REVIEW 3 major objections 4 minor 37 references
Cutoff for random lifts of weighted graphs
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Random walks on uniform random n-lifts of an irreducible weighted graph with at least two oriented cycles mix in time $h^{-1}\log n$ with a cutoff window of order $\sqrt{\log n}$.
desk verdict Genuinely new and significant result, but as written it overclaims the full A.1/A.2 theorem because Section 5.1's speed claim for one-way directed graphs is off by a factor of two. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The universal cover $(T_{\mathcal{G}}, \circ)$, the infinite rooted tree obtained by unfolding all non-backtracking paths of $\mathcal{G}$, is the central object; its entropy $h$ is the asymptotic rate of the log-weight $W_t=-\log W(X_t)$, where $W(x)$ is the probability that a walk from the root has $x$ on its loop-erased ray to infinity. The engine of the proof is Theorem 3, a CLT for $W_t$ obtained by cutting the walk into i.i.d. excursions between exit edges, giving the constants $h$ and $\sigma$. The upper bound then couples a walk on the universal cover to a walk on the lift until cycles are met, uses local exploration and ray localization to control coupling failure, and finishes with the expansion of random lifts to force the last jump to equilibrium.
What would settle it
Simulate the random walk on random $n$-lifts of a base graph satisfying A.1 and A.2 but violating A.4, such as a two-cycle core with an attached leaf, measure $t_{\max}(\varepsilon)$ for increasing $n$, and compare it with $h^{-1}\log n$ computed from the formulas in Section 6; if the ratio does not approach $1$, the Section 5 reduction is invalid.
Extended reading notes
Core claim
Theorem 1 states that, under assumptions A.1 and A.2, for any $\varepsilon\in(0,1)$ the worst-case $\varepsilon$-mixing time of the random walk on a uniform random $n$-lift satisfies $t_{\max}(\varepsilon)=h^{-1}\log n+O_P(\sqrt{\log n})$, with $h>0$ the entropy of the universal cover of $\mathcal{G}$. Proposition 2 adds that for any deterministic sequence of $n$-lifts, the best-case mixing time is asymptotically at least $h^{-1}\log n$, so random lifts attain the smallest possible mixing time among all lifts. The proof is carried out under auxiliary assumptions A.3 and A.4, then extended to all graphs satisfying A.1 and A.2 by a reduction in Section 5 whose details are largely left to the reader.
Load-bearing premise
The main theorem is stated for all graphs satisfying A.1 and A.2, but the main proof assumes A.3 and A.4, and the extension to graphs with zero-weight orientations or attached trees depends on an unproved reduction in Section 5 that is justified only by phrases such as 'one checks readily' and 'details are left to the reader'; if that reduction is wrong, the cutoff formula does not follow for those graphs.
Editorial extensions
If this is right
- For every $\varepsilon\in(0,1)$, the ratio $t_{\max}(\varepsilon)/(h^{-1}\log n)$ converges in probability to $1$, giving a sharp cutoff with window of order $\sqrt{\log n}$.
- Random $n$-lifts are optimal among all $n$-lifts: any deterministic lift has best-case $\varepsilon$-mixing time at least $h^{-1}\log n$ in the same asymptotic sense.
- The cutoff holds without assuming reversibility of the walk on the base graph, and more generally for lazy walks with holding probability $\alpha\in(0,1)$, with entropy $h_\alpha=h/(2(1-\alpha))$.
- When $\mathcal{G}$ is a single vertex with $d/2$ loops, the result recovers the Lubetzky--Sly cutoff for $d$-regular random graphs, with mixing time $((d-2)\log(d-1)/d)^{-1}\log n$.
- The theorem yields sequences of non-weakly-Ramanujan expanders on which the simple random walk nonetheless has a cutoff.
Reading between the lines
- The lower bound in the paper suggests, and the authors conjecture, a Gaussian profile for the cutoff window; an immediate testable extension is to prove full Gaussian fluctuation at the scale $\sqrt{\log n}$.
- One could probe whether the upper bound for holding probability $\alpha=0$ holds beyond the $d$-regular case; the paper proves the lower bound and derives the $d$-regular upper bound by taking $\alpha\to 0$, but leaves the general window open.
- The theorem hints that for any finite irreducible Markov chain with positive holding probability, imposing a random covering structure makes the global mixing time depend only on the entropy of the universal cover, decoupling it from spectral or geometric details of the base chain.
- A numerical check on small non-reversible base graphs with attached trees would be a cheap way to test whether the unproved Section 5 reduction preserves both the entropy constant and the cutoff.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the mixing time of the random walk on a uniform random n-lift of a finite weighted multigraph G. The main result, Theorem 1, states that under irreducibility (A.1) and a two-cycles condition (A.2), the worst-case epsilon-mixing time is w.h.p. h^{-1} log n + O_P(sqrt(log n)), where h is the entropy of the universal cover of G, and that this is optimal among all lifts by Proposition 2. The proof is conducted under two additional hypotheses, A.3 (all oriented edges have positive weight) and A.4 (every oriented edge lies on an oriented cycle), and rests on a CLT for the entropic weight on the universal cover (Theorem 3), an excursion decomposition with exponential tails (Proposition 19), a coupling of the walk on the lift with the walk on the universal cover, a spectral last step, and an all-starting-points extension. Section 5 claims to remove A.3 and A.4, stating that this is done by direct reductions. The paper also claims an extension to arbitrary holding probability with the entropy rescaling h_alpha = h/(2(1-alpha)) in Eq. (3), and uses this in the d-regular example and in the discussion of the non-lazy case alpha=0.
Significance. If the main theorem is correct, the paper gives a substantial and elegant extension of the cutoff phenomenon to random lifts of non-reversible weighted graphs, with a sharp sqrt(log n) window and an optimality statement for random lifts among all lifts. The technical core under A.3 and A.4 is genuinely nontrivial: the transience criterion, the renewal/excursion structure, and the CLTs for the entropic weight and the height (Theorem 3 and Proposition 20) are proved in detail, and the lower bound is shown to hold uniformly for all lifts. The paper also correctly highlights the relevance of the universal cover and the non-backtracking random walk on the derived graph. However, the advertised scope of Theorem 1 goes beyond what is proved, because the removal of A.3 in Section 5.1 contains a concrete internal inconsistency, and the removal of A.4 in Section 5.2 is only sketched. These issues are load-bearing for the theorem as stated, so a revision is necessary before the full result can be accepted.
major comments (3)
- [§5.1 and §4.2(c)] The claim in §5.1 that 'if A.3* is not verified, Proposition 20 becomes he(X_t)=t a.s. (hence s=1)' contradicts the transition rule fixed in §1.2, which is P_G(u,v)=1/2 1_{u=v}+1/2 sum w(e). In the universal cover of a graph with no edge having both orientations positive, the reverse of the incoming oriented edge has weight 0, so every non-lazy step increases the height by exactly 1. The number of non-lazy steps up to time t is Binomial(t,1/2), so he(X_t)/t -> 1/2 a.s., not 1. This is not a harmless typographical slip: Proposition 25 in §4.2(c) sets c=3/(2s) and requires P(4r/3 <= he(X_{floor(cr)}) <= 5r/3) >= 1-delta. With the stated s=1 one has c=3/2, and under the correct speed the expected height after 1.5r steps is about 0.75r, so the required event has probability tending to 0. Consequently the all-starting-points extension, and hence Theorem 1 for base graphs without A.3, is not proved as written.
- [§1.4, Eq. (3), and §7] Equation (3), h_alpha = h/(2(1-alpha)), is not consistent with the definition of the lazy chain P^(alpha) = alpha I + (1-alpha) sum w. Adding holding probability alpha does not change the loop-erased ray, so the ray weight h_W is unchanged and only the speed scales by (1-alpha). Thus, if h denotes the entropy for the paper's alpha=1/2 walk, the correct relation is h_alpha = 2(1-alpha) h, equivalently h_alpha = (1-alpha) h_0 with h_0 the non-lazy entropy. The printed formula gives the reciprocal behaviour. This matters concretely in §7, where the text states h_0 = h/2 according to (3) while simultaneously displaying t_mix = h_0^{-1} log n = (2h)^{-1} log n; the latter would require h_0 = 2h. The claimed derivation of the d-regular constant in §1.5 and the alpha -> 0 upper bound in §7 are therefore not supported by the stated relation.
- [§5.2] The main theorem is stated for all graphs satisfying A.1 and A.2, but Sections 3 and 4 prove it only under A.3 and A.4. The reduction in §5.2 that removes A.4 by passing to the core c(G) is asserted rather than proved: the CLT for the time spent in the core is stated without proof, and the transfer of the coupling, the almost-mixing corollary, and especially the all-starting-points arguments to the time-changed walk is not established. The sentence 'the excursion theory presented in Section 3.4 is still true' is a claim, not a proof. Since A.4 is part of the theorem's hypotheses, the full statement of Theorem 1 currently exceeds what is rigorously demonstrated in the manuscript.
minor comments (4)
- [§4.2(a), proof of Proposition 21] The inequality 'P(xi_{J0} notin N(beta)) >= 1 - epsilon/4' is inconsistent with its later use as an upper bound; it should read 'P(...) <= epsilon/4'.
- [§3.4, Lemma 8] The statement that the CLT for additive functionals holds 'and not requiring aperiodicity' is too quick; for periodic irreducible chains one must either separate residue classes or verify that the periodic oscillation is negligible in the specific applications. A citation of a theorem covering the periodic case would be helpful.
- [§4.2(a), proof of Corollary 5] The displayed computation of 1 - nu_n(V_n) contains several typographical artifacts, for example 'T T t'_n(deg, phi(x'),T)' and the definition of nu'_n, which should be cleaned up for readability.
- [§5.1] The sentence 'if A.3* is not verified' is confusing because A.3* is defined positively as the existence of an edge with both orientations positive; the intended meaning is 'if no edge has both orientations positive'.
Circularity Check
No significant circularity: the entropic-time result is self-contained and not forced by fitted parameters or self-citation.
full rationale
The paper defines h purely from the universal cover of G via a CLT for the entropic weight W_t = -log W(X_t) and computes it through standard Green-function equations, with no parameter fitted to mixing-time data. The lower and upper bounds both involve this same h, but that reflects the theorem's content (the entropic time is the mixing time), not a circular construction. The d-regular case is checked against the independent Lubetzky-Sly constant, which is an external benchmark. The cited results from Nagnibeda-Woess, Lalley, and Gilch are external, not self-citations, and are used for transience, CLTs, and speed formulas; the paper does not import a uniqueness theorem from itself. The main weakness is a correctness issue in Section 5.1, where the assertion that he(X_t)=t a.s. and s=1 under A.3* appears inconsistent with the 1/2-lazy transition rule fixed in Section 1.2; that would undermine the proof of Theorem 1 for the relaxed class, but it is an internal consistency problem, not a circular reduction of the result to its own inputs. No equation in the paper is shown to be equivalent to another by construction, and no fitted parameter is renamed as a prediction. Hence the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math The Green function and speed results of Nagnibeda-Woess [33] and Lalley [23] apply to periodic trees arising from weighted graphs: exponential decay of P_T^n(x,x), the CLT for rate of escape, and the system of equations for first-passage Green functions.
- standard math The additive reversibilization criterion of Gaudilliere-Landim [19, Lemma 5.1] is valid for the non-reversible random walk on the universal cover with invariant measure pi~.
- domain assumption The conductance lower bound for random lifts from Amit-Linial [5] extends to non-reversible weighted walks as stated in Proposition 22.
- ad hoc to paper For any G satisfying A.1 and A.2, the reduction in Section 5 from G to a core c(G) satisfying A.3/A.4 preserves the mixing time up to the factor a h, where a is the asymptotic fraction of time spent in the core.
Cite this review
Pith. "Pith review of Cutoff for random lifts of weighted graphs." pith.science (2026). https://pith.science/paper/MXZO4CDQ
@misc{pith2026190802898,
author = {Pith},
title = {Pith review of: Cutoff for random lifts of weighted graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/MXZO4CDQ}},
note = {Machine review of arXiv:1908.02898}
}
abstract
We prove a cutoff for the random walk on random $n$-lifts of finite weighted graphs, even when the random walk on the base graph $\mathcal{G}$ of the lift is not reversible. The mixing time is w.h.p. $t_{mix}=h^{-1}\log n$, where $h$ is a constant associated to $\mathcal{G}$, namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all $n$-lifts of $\mathcal{G}$. In the particular case where the base graph is a vertex with $d/2$ loops, $d$ even, we obtain a cutoff for a $d$-regular random graph (as did Lubetzky and Sly in \cite{cutoffregular} with a slightly different distribution on $d$-regular graphs, but the mixing time is the same).
Figures
Reference graph
Works this paper leans on
-
[1]
Louigi Addario-Berry and Simon Griffiths. The spectrum of random lifts. arXiv e-prints , page arXiv:1012.4097, Dec 2010
arXiv 2010
-
[2]
Random walks on finite groups and rapidly mi xing markov chains
David Aldous. Random walks on finite groups and rapidly mi xing markov chains. In Jacques Az´ ema and Marc Yor, editors, S´ eminaire de Probabilit´ es XVII 1981/82, pages 243–297, Berlin, Heidelberg, 1983. Springer Berlin Heidel berg
work page 1981
-
[3]
Shuffling cards and stopp ing times
David Aldous and Persi Diaconis. Shuffling cards and stopp ing times. Amer. Math. Monthly, 93(5):333–348, 1986
work page 1986
-
[4]
N Alon and V.D. Milman. Eigenvalues, expanders and super concentrators, 11 1984
work page 1984
-
[5]
Random lifts of graphs: edge expansion
Alon Amit and Nathan Linial. Random lifts of graphs: edge expansion. Combin. Probab. Comput., 15(3):317–332, 2006. 35
work page 2006
-
[6]
Random lifts of graphs: independence and chromatic number
Alon Amit, Nathan Linial, and Jiˇ r ´ ı Matouˇ sek. Random lifts of graphs: independence and chromatic number. Random Structures Algorithms , 20(1):1–22, 2002
work page 2002
-
[7]
Alon Amit, Nathan Linial, Jiˇ r ´ ı Matouˇ sek, and Eyal Rozenman. Random lifts of graphs. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discre te Algorithms (Wash- ington, DC, 2001) , pages 883–894. SIAM, Philadelphia, PA, 2001
work page 2001
-
[8]
Random walks on dynamic configuration models: a trichotomy
Luca Avena, Hakan Guldas, Remco van der Hofstad, and Fran k den Hollander. Ran- dom walks on dynamic configuration models: a trichotomy. arXiv e-prints , page arXiv:1803.04824, Mar 2018
work page Pith review arXiv 2018
Show all 37 references
-
[9]
Compari ng mixing times on sparse random graphs
Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Compari ng mixing times on sparse random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1734–1740. SIAM, Philadelphia, PA, 2018
2018
-
[10]
Cutoff for nonbacktrac king random walks on sparse random graphs
Anna Ben-Hamou and Justin Salez. Cutoff for nonbacktrac king random walks on sparse random graphs. Ann. Probab., 45(3):1752–1770, 2017
2017
-
[11]
Random walks on the random graph
Nathana¨ el Berestycki, Eyal Lubetzky, Yuval Peres, an d Allan Sly. Random walks on the random graph. Ann. Probab., 46(1):456–490, 01 2018
2018
-
[12]
Bordenave
C. Bordenave. A new proof of Friedman’s second eigenval ue Theorem and its extension to random lifts. ArXiv e-prints , February 2015
2015
-
[13]
Eigenvalues of random lifts and polynomial of random permutations matrices
Charles Bordenave and Beno ˆ ıt Collins. Eigenvalues of random lifts and polynomial of random permutations matrices. arXiv e-prints , page arXiv:1801.00876, Jan 2018
2018 arXiv
-
[14]
Cutoff at the entro pic time for random walks on covered expander graphs
Charles Bordenave and Hubert Lacoin. Cutoff at the entro pic time for random walks on covered expander graphs. arXiv e-prints , page arXiv:1812.06769, Dec 2018
2018 arXiv
-
[15]
Mixing time of Pa geRank surfers on sparse random digraphs
Pietro Caputo and Matteo Quattropani. Mixing time of Pa geRank surfers on sparse random digraphs. arXiv e-prints , page arXiv:1905.04993, May 2019
1905 arXiv
-
[16]
Markov chains with stationary transition probabilities
Kai Lai Chung. Markov chains with stationary transition probabilities . Die Grundlehren der mathematischen Wissenschaften, Bd. 104. Springer-Verlag , Berlin-G¨ ottingen-Heidelberg, 1960
1960
-
[17]
Generating a r andom permutation with ran- dom transpositions
Persi Diaconis and Mehrdad Shahshahani. Generating a r andom permutation with ran- dom transpositions. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwand te Gebiete , 57(2):159–179, Jun 1981
1981
-
[18]
Minors in lifts of graphs
Yotam Drier and Nathan Linial. Minors in lifts of graphs . Random Structures Algorithms , 29(2):208–225, 2006. 36
2006
-
[19]
Gaudilli` ere and C
A. Gaudilli` ere and C. Landim. A dirichlet principle fo r non reversible markov chains and some recurrence theorems. Probability Theory and Related Fields , 71(1):55–89, Feb 2001
2001
-
[20]
Lorenz A. Gilch. Rate of escape of random walks on regula r languages and free products by amalgamation of finite groups. In Fifth Colloquium on Mathematics and Computer Science, DMTCS Proc , pages 2544–2560, 2008
2008
-
[21]
Lorenz A. Gilch. Asymptotic entropy of random walks on r egular languages over a finite alphabet. Electron. J. Probab. , 21:Paper No. 8, 42, 2016
2016
-
[22]
Cutoff for Mixing Times o n Random Abelian Cayley Graphs
Jonathan Hermon and Sam Thomas. Cutoff for Mixing Times o n Random Abelian Cayley Graphs. arXiv e-prints , page arXiv:1810.05130, Oct 2018
2018 arXiv
-
[23]
Steven P. Lalley. Random walks on regular languages and algebraic systems of generating functions. In Algebraic methods in statistics and probability (Notre Dam e, IN, 2000) , volume 287 of Contemp. Math. , pages 201–230. Amer. Math. Soc., Providence, RI, 2001
2000
-
[24]
Random lifts of graphs : perfect matchings
Nathan Linial and Eyal Rozenman. Random lifts of graphs : perfect matchings. Combina- torica, 25(4):407–424, 2005
2005
-
[25]
Cutoff on all Ramanujan gr aphs
Eyal Lubetzky and Yuval Peres. Cutoff on all Ramanujan gr aphs. arXiv e-prints , page arXiv:1507.04725, Jul 2015
2015 arXiv
-
[26]
Cutoff phenomena for random walks on random regular graphs
Eyal Lubetzky and Allan Sly. Cutoff phenomena for random walks on random regular graphs. Duke Math. J. , 153(3):475–510, 2010
2010
-
[27]
Spectra of lif ted ramanujan graphs
Eyal Lubetzky, Benny Sudakov, and Van Vu. Spectra of lif ted ramanujan graphs
-
[28]
Discrete groups, expanding graphs and invariant measures , volume 125 of Progress in Mathematics
Alexander Lubotzky. Discrete groups, expanding graphs and invariant measures , volume 125 of Progress in Mathematics . Birkh¨ auser Verlag, Basel, 1994. With an appendix by Jonathan D. Rogawski
1994
-
[29]
Random walks and percolation on trees
Russell Lyons. Random walks and percolation on trees. Ann. Probab., 18(3):931–958, 1990
1990
-
[30]
A simple criterion for transience of a reve rsible Markov chain
Terry Lyons. A simple criterion for transience of a reve rsible Markov chain. Ann. Probab., 11(2):393–402, 1983
1983
-
[31]
Mathematical aspec ts of mixing times in Markov chains
Ravi Montenegro and Prasad Tetali. Mathematical aspec ts of mixing times in Markov chains. Found. Trends Theor. Comput. Sci. , 1(3):x+121, 2006
2006
-
[32]
Gree n functions on trees with finitely many cone types, 1999
Tatiana Nagnibeda, Stockholm Sweeden, and A M S-t. Gree n functions on trees with finitely many cone types, 1999
1999
-
[33]
Random walks on t rees with finitely many cone types
Tatiana Nagnibeda and Wolfgang Woess. Random walks on t rees with finitely many cone types. J. Theoret. Probab., 15(2):383–422, 2002. 37
2002
-
[34]
The rate of escape for ani sotropic random walks in a tree
Stanley Sawyer and Tim Steger. The rate of escape for ani sotropic random walks in a tree. Probability Theory and Related Fields , 76(2):207–230, Oct 1987
1987
-
[35]
Cutoff for Random Walk on Dyna mical Erd¨os-R\’enyi Graph
Perla Sousi and Sam Thomas. Cutoff for Random Walk on Dyna mical Erd¨os-R\’enyi Graph. arXiv e-prints , page arXiv:1807.04719, Jul 2018
2018 arXiv
-
[36]
Random walk on periodic trees
Christiane Takacs. Random walk on periodic trees. Electron. J. Probab. , 2:16 pp., 1997
1997
-
[37]
Random walks and periodic continued fr actions
Wolfgang Woess. Random walks and periodic continued fr actions. Adv. in Appl. Probab. , 17(1):67–84, 1985. 38
1985
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.