{"id":"aa84da8d-0d63-4f5c-9607-35f47328da64","arxiv_id":"1908.02898","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random walks on random n-lifts of any irreducible weighted base graph with two oriented cycles mix at time h^{-1} log n with cutoff, h the universal-cover entropy.","lead":"This paper proves that a random walk on a random n-fold cover of any finite weighted graph mixes at the same universal time with sharp cutoff behavior, even when the original graph's walk is not reversible. The result also shows the random cover is the fastest possible mixer among all covers and recovers known cutoff results for random regular graphs as a special case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5.1 asserts s=1 for directed base graphs with no bidirectional edge, contradicting the 1/2-lazy walk defined in §1.2; the A.3 relaxation used by Theorem 1 is therefore not established as written.","rationale":"The reader identified Section 5's removal of A.3/A.4 as the weakest assumption; I agree that the main theorem's full generality rests on that sketch. The more specific problem is that Section 5.1's excepted case contains a false speed statement for the very dynamics used in the paper. This is not a stylistic issue: Section 4.2(c) chooses the constant c from s and relies on a level-crossing event whose probability collapses if s=1/2 instead of 1, so the proof of the worst-case extension genuinely fails for graphs without A.3*. The issue is fixable — replace s by the actual speed and choose c accordingly — and the theorem may be salvageable, which is why I keep the reader's CONDITIONAL verdict rather than rejecting the paper. A numerical check on a concrete directed base graph would settle the internal inconsistency immediately. No machine-checked proof, parameter fitting, or circularity is involved; the concern is purely about the written argument.","tokens_in":31119,"tokens_out":30106,"duration_ms":365287,"concrete_test":"Take a directed base graph satisfying A.1 and A.2 but not A.3*, for example two directed 3-cycles sharing a vertex, all edge weights 1/outdegree, plus the §1.2 holding probability 1/2. Simulate the walk on its universal cover from the root for T=10^7 steps and estimate he(X_T)/T. If the slope is ≈1/2 rather than 1, Section 5.1's assertion s=1 is false. Then, for r=20, run the same walk for t=⌊(3/2)r⌋ steps and measure the frequency of {4r/3 ≤ he(X_t) ≤ 5r/3}; a frequency near 0 confirms that Proposition 25's constant fails under the true speed, so the proof needs a corrected s and c.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 is stated for all graphs satisfying A.1 and A.2, but Sections 3-4 prove it only under A.3 and A.4. Section 5.1 removes A.3 and claims that when A.3* fails (no edge has both orientations positive), Proposition 20 becomes he(X_t)=t a.s., hence s=1. This is inconsistent with the paper's own transition rule: §1.2 fixes P_G(u,v)=1/2 1_{u=v}+1/2 Σ w(e), and the same holding probability is used in Sections 3 and 4. In the universal cover of a strongly connected directed graph with no bidirectional edge, every positive-weight transition goes to a new child, because the reverse of the incoming edge has weight 0; therefore height increases by 1 only on the non-lazy half of the steps, so the asymptotic speed is 1/2, not 1. The proof of Proposition 25 in §4.2(c) sets c=3/(2s) and requires P(4r/3 ≤ he(X_{⌊cr⌋}) ≤ 5r/3) ≥ 1-δ. With the claimed s=1, c=3/2, so after 1.5r steps the correct speed gives expected height ≈0.75r and the required event has probability about 0. The all-starting-points extension, and hence Theorem 1 for this class, is not proved as written. This is an internal consistency problem, not a disagreement with consensus.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31419,"tokens_out":36965,"duration_ms":401224,"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":[{"comment":"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.","section":"§5.1 and §4.2(c)"},{"comment":"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.","section":"§1.4, Eq. (3), and §7"},{"comment":"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.","section":"§5.2"}],"minor_comments":[{"comment":"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'.","section":"§4.2(a), proof of Proposition 21"},{"comment":"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.","section":"§3.4, Lemma 8"},{"comment":"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.","section":"§4.2(a), proof of Corollary 5"},{"comment":"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'.","section":"§5.1"}],"recommendation":"major_revision","confidential_remarks":"The core method is strong and the proofs under A.3/A.4 are substantial, so rejection is not warranted. However, the paper's advertised theorem cannot be accepted until the inconsistencies in Section 5.1 and Eq. (3) are fixed and the A.4 reduction in Section 5.2 is either fully proved or explicitly excluded from the theorem statement. I would expect a careful revision to be able to address these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main theorem here is genuinely new and important: it removes the reversibility and uniform-invariant-measure assumptions that bounded all prior work on cutoff for random lifts, and Proposition 2's best-case lower bound for arbitrary lifts is a nice addition. Under the auxiliary assumptions A.3 and A.4, the proof is detailed, largely self-contained, and credible—the transience criterion, excursion decomposition, and CLT for the log-weight are all genuinely proved. The d-regular special case matches Lubetzky–Sly's constant, which is an honest external check, and there are no fitted parameters or circular steps.\n\nBut the paper as stated claims Theorem 1 for all graphs satisfying A.1 and A.2, and that full claim is not established. The soft spot is Section 5.1, and the stress-test note lands. The paper's own transition rule (Section 1.2) is 1/2-lazy: the walk stays put with probability 1/2 and moves with probability 1/2. When A.3* fails — no edge has both orientations positive — every positive-weight transition in the universal cover is to a child, so height increases only on the non-lazy half of the steps. The asymptotic speed is s = 1/2, not s = 1 as claimed in Section 5.1. This matters directly: Proposition 25 sets c = 3/(2s), and with the claimed s = 1 the required event {4r/3 ≤ he(X_{⌊cr⌋}) ≤ 5r/3} has probability tending to 0, not 1. The all-starting-points extension, and hence Theorem 1 for this class, is not proved as written. The fix is straightforward — replace s by 1/2 and c by 3 — but it has to be written down and checked through. Separately, Section 5's removal of A.3 and A.4 is sketched with \"one checks readily\" and \"details are left to the reader\"; a referee should ask for those details.\n\nThis is a real contribution and deserves a serious referee. I would recommend conditional acceptance or major revision: the core ideas and the proofs under A.3/A.4 are solid, and the issues are correctable. A corrected version would be a strong paper. The reader's conditional verdict is about right, and the stress-test concern is a genuine internal inconsistency rather than a disagreement with consensus.","headline":"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.","tokens_in":31949,"tokens_out":6329,"would_cite":true,"duration_ms":66000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","05C80","60F05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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}$.","keywords":["cutoff phenomenon","random n-lifts","weighted graphs","random walks","mixing time","universal cover","entropy","expander graphs"],"falsifier":"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.","tokens_in":30844,"feed_emoji":"🎲","tokens_out":5646,"duration_ms":60188,"temperature":0.7,"pith_summary":"The paper claims that for every finite weighted multigraph $\\mathcal{G}$ whose random walk is irreducible and which has at least two oriented cycles not each other's inverse, the random walk on a uniform random $n$-lift of $\\mathcal{G}$ exhibits a sharp cutoff: the worst-case $\\varepsilon$-mixing time is $h^{-1}\\log n + O_P(\\sqrt{\\log n})$, where $h$ is the entropy of the universal cover of $\\mathcal{G}$. This matters because it makes the cutoff phenomenon available for a very wide family of sparse random graphs, including base walks that are not reversible, and shows that random lifts are optimal: no deterministic $n$-lift can mix faster than $h^{-1}\\log n$. A sympathetic reader should take the theorem as the paper's central assertion: random covering structure alone produces a precise, universal mixing-time law governed by the base graph's universal cover.","feed_headline":"Random lift walks hit cutoff exactly at the entropic time","feed_subtitle":"For every irreducible weighted graph with two cycles, no lift can mix faster, and the window is only sqrt(log n).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the benchmark result for $d$-regular random graphs that the paper recovers and matches as a special case.","marker":"[26]"},{"why":"Establishes the earlier cutoff at the entropic time for reversible walks with uniform invariant measure, which this paper generalizes.","marker":"[14]"},{"why":"Provides the edge-expansion of random lifts used in Proposition 22 for the spectral finishing step.","marker":"[5]"},{"why":"Supplies the coupling and almost-mixing strategy for random graphs that is adapted here to walks on lifts.","marker":"[11]"},{"why":"Provides the Green-function and cone-type tree theory used for transience, speed, and entropy of the universal cover.","marker":"[33]"},{"why":"Identifies the asymptotic entropy and gives computational formulas via random walks on regular languages.","marker":"[21]"},{"why":"Gives the exponential-decay estimates for transition probabilities on regular languages used in Section 3.4.","marker":"[23]"},{"why":"Supplies the argument that reversibility is not needed once an invariant measure exists, extending the tree results to non-reversible base walks.","marker":"[19]"},{"why":"Provides the electrical-network transience criterion used to prove transience of the walk on the universal cover.","marker":"[30]"},{"why":"Supplies the conductance-based $L^2$ contraction used in the final mixing step and discussed in the laziness appendix.","marker":"[31]"}],"fun_headline_variants":["Random lifts mix at entropic cutoff, unbeatable","Entropy of universal cover sets cutoff for random lifts","Random lifts achieve the optimal entropic mixing time","Cutoff on random lifts: entropic time is the floor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random lifts mix at entropic cutoff, unbeatable","Entropy of universal cover sets cutoff for random lifts","Random lifts achieve the optimal entropic mixing time","Cutoff on random lifts: entropic time is the floor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001006,"raw_usage":{"total_tokens":4212,"prompt_tokens":862,"completion_tokens":3350,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":3286}},"tokens_in":478,"tokens_out":3350,"duration_ms":23452,"temperature":1.0,"reasoning_tokens":3286,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:32:10.583151+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Cutoff phenomena for random walks on random regular graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the benchmark result for $d$-regular random graphs that the paper recovers and matches as a special case."},{"cited_title":"Cutoff at the entropic time for random walks on covered expander graphs","cited_arxiv_id":"1812.06769","evidence_quote":"Establishes the earlier cutoff at the entropic time for reversible walks with uniform invariant measure, which this paper generalizes."},{"cited_title":"Random lifts of graphs: edge expansion","cited_arxiv_id":null,"evidence_quote":"Provides the edge-expansion of random lifts used in Proposition 22 for the spectral finishing step."},{"cited_title":"Random walks on the random graph","cited_arxiv_id":null,"evidence_quote":"Supplies the coupling and almost-mixing strategy for random graphs that is adapted here to walks on lifts."},{"cited_title":"Random walks on t rees with finitely many cone types","cited_arxiv_id":null,"evidence_quote":"Provides the Green-function and cone-type tree theory used for transience, speed, and entropy of the universal cover."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies the asymptotic entropy and gives computational formulas via random walks on regular languages."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the exponential-decay estimates for transition probabilities on regular languages used in Section 3.4."},{"cited_title":"Gaudilli` ere and C","cited_arxiv_id":null,"evidence_quote":"Supplies the argument that reversibility is not needed once an invariant measure exists, extending the tree results to non-reversible base walks."},{"cited_title":"A simple criterion for transience of a reve rsible Markov chain","cited_arxiv_id":null,"evidence_quote":"Provides the electrical-network transience criterion used to prove transience of the walk on the universal cover."},{"cited_title":"Mathematical aspec ts of mixing times in Markov chains","cited_arxiv_id":null,"evidence_quote":"Supplies the conductance-based $L^2$ contraction used in the final mixing step and discussed in the laziness appendix."}],"review_version":1}