arxiv: 2605.09229 · v2 · submitted 2026-05-09 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Average Hitting Times and Recurrence Structures I: Powers of Cycle Graphs

Shunya Tamura, Tsuyoshi Miezaki

Pith reviewed 2026-05-13 06:12 UTC · model grok-4.3

classification 🧮 math.CO

keywords average hitting timescycle power graphsrandom walksrecurrence sequenceseffective resistancespanning treesgraph Laplacian

0 comments

The pith

Average hitting times on powers of cycle graphs decompose into a quadratic term plus finitely many recurrence-sequence corrections from the Laplacian operator.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives explicit formulas for the average hitting times of simple random walks on the k-th power of a cycle graph C_N^k. It begins with the difference equation supplied by the graph Laplacian, exploits the cyclic symmetry to obtain a Fourier spectral representation, and then factors the difference operator so that partial fraction decomposition produces a closed form. The resulting expression consists of a quadratic term in the vertex distance together with correction terms that satisfy second-order linear recurrences whose characteristic polynomials arise from the factorization; these recurrences generalize Fibonacci-type sequences. The same formulas immediately yield closed expressions for effective resistances, the number of spanning trees, the number of two-component spanning forests, and the number of spanning trees after vertex identification.

Core claim

The average hitting time on C_N^k satisfies the Laplacian difference equation; cyclic Fourier analysis reduces it to a rational function of the eigenvalues, and factorization of the corresponding difference operator followed by partial fraction decomposition expresses the solution as a quadratic particular solution plus homogeneous solutions that are linear recurrence sequences of order at most two associated with the characteristic polynomials of the factors.

What carries the argument

Factorization of the difference operator arising from the graph Laplacian on C_N^k, followed by partial fraction decomposition that isolates second-order linear recurrence sequences.

Load-bearing premise

The cyclic symmetry of the graph permits a complete spectral representation, and the difference operator factors in a way that allows partial fraction decomposition into terms solvable by recurrence sequences.

What would settle it

For fixed small N and k, solve the linear system for hitting times directly from the Laplacian matrix and compare the numerical values against the closed-form quadratic-plus-recurrence expression obtained from the factorization.

read the original abstract

We investigate the average hitting times of simple random walks on the $k$-th power graph $C_N^k$ of the cycle graph $C_N$. First, we show that the average hitting times are characterized by a difference equation corresponding to the graph Laplacian. Next, by using the cyclic symmetry of $C_N^k$, we derive a spectral representation via Fourier analysis. Furthermore, by applying factorization and partial fraction decomposition of the corresponding difference operator, we obtain an explicit formula for the average hitting times consisting of a quadratic term and finitely many correction terms. These correction terms are described by second-order linear recurrence sequences associated with the characteristic polynomials, and can be regarded as natural generalizations of Fibonacci-type sequences. As a consequence, our formulas recover the known results for cycle graphs and squares of cycle graphs in a unified way. Moreover, from the formulas obtained for average hitting times, we derive explicit formulas for the effective resistances, the numbers of spanning trees, the numbers of two-component spanning forests, and the numbers of spanning trees of vertex-identified graphs. In particular, for the third power graph $C_N^3$ of the cycle graph, all of these quantities are written explicitly in terms of complex conjugate Fibonacci-type sequences. Our results clarify structural relations between random walk quantities and combinatorial quantities on cycle power graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit closed-form hitting times on C_N^k via partial fractions on the circulant Laplacian, recovering the k=1 and k=2 cases and feeding directly into spanning-tree and resistance formulas.

read the letter

The main contribution is a unified explicit formula for average hitting times on the k-th power of the cycle: a quadratic term plus a finite sum of terms from second-order linear recurrences whose characteristic polynomials come from factoring the symbol of the difference operator. This recovers the known expressions for ordinary cycles and their squares without separate cases, and the same expressions immediately yield closed forms for effective resistances, spanning-tree counts, two-component forests, and trees on vertex-identified graphs. For k=3 they spell everything out with complex-conjugate Fibonacci-type sequences, which is concrete and checkable.

Referee Report

2 major / 2 minor

Summary. The paper derives explicit formulas for average hitting times of simple random walks on the k-th power C_N^k of the cycle graph. It begins with the inhomogeneous difference equation induced by the graph Laplacian, exploits cyclic symmetry to obtain a Fourier spectral representation, factors the resulting circulant symbol (which is reciprocal), and applies partial-fraction decomposition to express the hitting time as a quadratic particular solution plus a linear combination of k second-order linear recurrence sequences whose characteristic polynomials arise from the quadratic factors r^2 - z_i r + 1. The same expressions are then used to obtain closed forms for effective resistances, the number of spanning trees, the number of two-component spanning forests, and the number of spanning trees in vertex-identified graphs; the k=1 and k=2 cases recover the known literature, while the k=3 case is written in terms of complex-conjugate Fibonacci-type sequences.

Significance. If the algebraic derivations are correct, the manuscript supplies a uniform, parameter-free method that links hitting times on any circulant graph with symmetric steps to combinatorial invariants via recurrence sequences. The approach is intrinsic to the reciprocal structure of the symbol and therefore extends immediately to other circulant families; the explicit recovery of prior results for small k and the concrete formulas for k=3 constitute verifiable strengths.

major comments (2)

[§3.2] §3.2, after Eq. (3.4): the factorization into k quadratics is asserted once the substitution z = r + 1/r is made, but the manuscript does not exhibit the explicit roots z_i or prove that all roots of the degree-2k symbol lie on the unit circle (or come in reciprocal pairs) for arbitrary k; a short inductive or resultant argument would remove any doubt that the partial-fraction step is always well-defined.
[§4.1] §4.1, Eq. (4.7): the inhomogeneous term that produces the quadratic particular solution is taken to be constant after Fourier inversion, yet the precise normalization of the Green function (or the choice of reference vertex) is not restated; without this, it is unclear whether the quadratic coefficient is exactly 1/(2k) or carries an extra factor depending on N.

minor comments (2)

The recurrence sequences are introduced as “generalized Fibonacci-type”; a single sentence recalling the standard Binet-style closed form for each quadratic factor would make the final expressions for k=3 immediately usable by readers.
Table 1 (numerical checks) reports only three values of N per k; adding one more column for a larger N (e.g., N=100) would strengthen the claim that the recurrence formulas are numerically stable.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the positive recommendation for minor revision. We address the major comments point by point below.

read point-by-point responses

Referee: [§3.2] §3.2, after Eq. (3.4): the factorization into k quadratics is asserted once the substitution z = r + 1/r is made, but the manuscript does not exhibit the explicit roots z_i or prove that all roots of the degree-2k symbol lie on the unit circle (or come in reciprocal pairs) for arbitrary k; a short inductive or resultant argument would remove any doubt that the partial-fraction step is always well-defined.

Authors: We agree that an explicit verification strengthens the presentation. In the revised manuscript we have inserted a short inductive argument immediately after Eq. (3.4). The induction shows that the reciprocal symbol of degree 2k factors into k quadratic factors whose roots lie on the unit circle, using the positivity of the coefficients of the circulant symbol to guarantee that all roots are distinct, lie on the unit circle, and appear in reciprocal pairs. revision: yes
Referee: [§4.1] §4.1, Eq. (4.7): the inhomogeneous term that produces the quadratic particular solution is taken to be constant after Fourier inversion, yet the precise normalization of the Green function (or the choice of reference vertex) is not restated; without this, it is unclear whether the quadratic coefficient is exactly 1/(2k) or carries an extra factor depending on N.

Authors: The reference vertex is fixed at vertex 0 by symmetry, and the Green function is normalized to vanish at this vertex. After Fourier inversion the inhomogeneous term is therefore the constant 1/(2k), so the quadratic particular solution has leading coefficient exactly 1/(2k) with no additional N-dependent factor. We have added a clarifying sentence in the revised §4.1 restating this normalization. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper begins with the standard characterization of average hitting times via the graph Laplacian difference equation on C_N^k, invokes the cyclic symmetry to obtain a Fourier spectral representation, and then factors the resulting circulant symbol (which is invariant under r to 1/r) into quadratics whose roots generate the second-order recurrence sequences for the correction terms. Partial fractions then yield the explicit closed form consisting of the quadratic particular solution plus the homogeneous corrections. All steps are algebraic identities intrinsic to symmetric circulant operators and require no external fitted parameters, no self-citation load-bearing premises, and no ansatz smuggled from prior work; the recovery of the k=1 and k=2 cases is a consistency check rather than an input. Subsequent formulas for effective resistances and spanning-tree counts are direct algebraic consequences of the hitting-time expression.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard properties of circulant graphs and linear recurrence theory; no free parameters are introduced, no new entities are postulated, and the axioms invoked are ordinary facts about the graph Laplacian and Fourier analysis on cyclic groups.

axioms (2)

domain assumption The k-th power of the cycle graph C_N is vertex-transitive and admits a complete set of eigenvectors given by the discrete Fourier basis.
Invoked to obtain the spectral representation of the hitting-time difference equation.
standard math The characteristic polynomial of the difference operator factors into linear terms over the complexes, permitting partial-fraction decomposition.
Used to reduce the solution to quadratic plus recurrence-sequence corrections.

pith-pipeline@v0.9.0 · 5532 in / 1540 out tokens · 144303 ms · 2026-05-13T06:12:54.194875+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Cost.FunctionalEquation, Foundation.DAlembert washburn_uniqueness_aczel; dAlembert_cosh_solution_aczel matches
by applying factorization and partial fraction decomposition of the corresponding difference operator... second-order linear recurrence sequences associated with the characteristic polynomials... V_n+1 = γ_a V_n - V_n-1
Constants, Foundation.AlphaDerivationExplicit phi_golden_ratio; phi3_eq echoes
for k=2... ρ = -φ^{-2}... V_n = (-1)^{n+1} F_{2n}

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Aldous and J.A

D. Aldous and J.A. Fill.Reversible Markov Chains and Random Walks on Graphs,

work page
[2]

Unfinished monograph:stat.berkeley.edu/ ~aldous/RWG/book.html

work page
[3]

Chaiken, A combinatorial proof of the all minors matrix tree theorem,SIAM J

S. Chaiken, A combinatorial proof of the all minors matrix tree theorem,SIAM J. Algebraic Discrete Methods3(1982), 319–329

work page 1982
[4]

Chair, The effective resistance of theN-cycle graph with four nearest neighbors, J

N. Chair, The effective resistance of theN-cycle graph with four nearest neighbors, J. Stat. Phys.154(2014), 1177–1190

work page 2014
[5]

Chandra, P

A.K. Chandra, P. Raghavan, W.L. Ruzzo, R. Smolensky, and P. Tiwari, The electrical resistance of a graph captures its commute and cover times,Proceedings of the 21st Annual ACM Symposium on Theory of Computing(1989), 574–586

work page 1989
[6]

Chebotarev and E

P. Chebotarev and E. Shamis, The matrix-forest theorem and measuring relations in small social groups,Autom. Remote Control58(1997), 1505–1514

work page 1997
[7]

Y. Doi, N. Konno, T. Nakamigawa, T. Sakuma, E. Segawa, H. Shinohara, S. Tamura, Y. Tanaka, and K. Toyota, On the average hitting times of the squares of cycles, Discrete Appl. Math.313(2022), 18–28

work page 2022
[8]

Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann

G. Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann. Phys. Chem. 72(1847), 497–508

work page
[9]

Mednykh and I.A

A.D. Mednykh and I.A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic,Discrete Math.342(2019), no. 6, 1772– 1781

work page 2019
[10]

Miezaki, A note on spanning trees,https://oeis.org/A331905/a331905.pdf

T. Miezaki, A note on spanning trees,https://oeis.org/A331905/a331905.pdf

work page
[11]

Miezaki and S

T. Miezaki and S. Tamura, Average hitting times and recurrence structures II, in preparation

work page
[12]

Miezaki and S

T. Miezaki and S. Tamura, Average hitting times and recurrence structures III, in preparation

work page
[13]

Nash-Williams, Random walk and electric currents in networks,Proc

C.S.J.A. Nash-Williams, Random walk and electric currents in networks,Proc. Cam- bridge Philos. Soc.55(1959), 181–194

work page 1959
[14]

Saloff-Coste and Y

L. Saloff-Coste and Y. Wang, Expected hitting time estimates on finite graphs,Sto- chastic Process. Appl.185 (2025), Paper No. 104626, 18 pp. 24

work page 2025
[15]

Szeg˝ o,Orthogonal polynomials, Amer

G. Szeg˝ o,Orthogonal polynomials, Amer. Math. Soc. Colloq. Publ., Vol. XXIII Amer- ican Mathematical Society, Providence, RI, 1975, xiii+432 pp

work page 1975
[16]

Wu, Theory of resistor networks: the two-point resistance,J

F.Y. Wu, Theory of resistor networks: the two-point resistance,J. Phys. A37(2004), 6653–6673. F aculty of Science and Engineering, W aseda University, Tokyo 169–8555, Japan Email address:miezaki@waseda.jp Okegawa City Okegawa West Junior High School, Saitama, 363-0027, Japan Email address:shunya.tamura059@gmail.com

work page 2004