{"id":"55f593c0-074f-4c92-bf8b-38bfc446f186","arxiv_id":"1908.08525","paper_version":4,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For reversible finite Markov chains, the L-infinity mixing time is at most trel log(e thit / trel), so the mixing time is comparable to the maximal hitting time exactly when the spectral gap times the hitting time remains bounded; this resolves the Aldous-Fill coalescence conjecture under…","lead":"New spectral-optimization inequalities show that the L-infinity mixing time of any finite reversible Markov chain is at most the relaxation time times a logarithm of the maximal hitting time. The bounds resolve a conjecture of Aldous and Fill about mean-field coalescence on vertex-transitive graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main spectral-optimization inequality is internally sound; the only load-bearing risk is the Aldous–Fill resolution's reliance on Oliveira [20], which the paper does not re-derive.","rationale":"I read Theorem 1 and its proof carefully. The spectral optimization approach is valid: the relaxed optimization problem has a maximizer, and the monotonicity of x^ell e^{-2xt} on [lambda_2, lambda_n] for t >= ell/(2 lambda_2) correctly forces the extremal configuration to concentrate all mass at lambda_2. The resulting inequalities (1.1)-(1.3) and Corollary 1.1 follow. I attempted to construct counterexamples (complete graph, star, barbell, n-cycle) and the bound behaves correctly; the Ding–Lubetzky–Peres birth-and-death example mentioned for sharpness is consistent. Theorems 3 and 4 are more elaborate, but the steps check out; the typographic issues noted above (the direction of monotonicity in Lemma 4.3 and the constant 2/3 in the transitive part of Theorem 4) do not change the mathematical content. The single genuinely load-bearing assumption for the 'resolves Aldous–Fill' headline is the correctness and exact scope of Oliveira [20], as the paper itself acknowledges. This is a normal external dependency rather than an internal flaw, so I do not move the reader's verdict. The reader's weakest_assumption identifies exactly this Oliveira reliance.","tokens_in":46,"tokens_out":26660,"duration_ms":382661,"concrete_test":"Retrieve Oliveira [20] and verify the precise statement flagged by the paper: the theorem at the top of p. 3423 and the two comments there. Check that (a) it applies to sequences of vertex-transitive graphs, (b) the hypothesis is exactly (t_TV_mix)^(n) << t_hit^(n), and (c) the conclusion is convergence in distribution of tau_coal/t_meet to the Kingman coalescent limit. Also check that the chain convention (continuous-time vs. lazy discrete-time) matches the present paper, and if Oliveira's proof requires an additional condition such as t_meet = Theta(t_hit), confirm that this holds for vertex-transitive chains with trel << t_hit. If all these checks pass, the Aldous–Fill resolution stands as claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's new contribution, Theorem 1 and Corollary 1.1, appears correct: the proof of (1.6)-(1.8) is a valid spectral relaxation, and the case analysis rules out all alternatives. What makes the headline 'resolves Aldous–Fill' load-bearing is the explicit external step: Oliveira [20] is quoted as having verified mean-field coalescence for vertex-transitive graphs under t_TV_mix << t_hit, and the paper only closes the gap between t_TV_mix << t_hit and trel << t_hit. That closure is legitimate: trel << t_hit implies t_mix^(inf) << t_hit by Corollary 1.1, hence t_TV <= t_inf << t_hit; conversely, (2.4) together with submultiplicativity gives trel <= (2/log 2) t_TV, so t_TV << t_hit implies trel << t_hit. However, the paper does not reproduce Oliveira's theorem, and the introduction attributes this equivalence to 'Theorem 3', whose statement concerns branching random walk hitting times, not the total-variation mixing time. If Oliveira's result had a gap, used a different chain convention (lazy discrete time vs. continuous time), or required a hypothesis other than t_TV_mix << t_hit, the conjecture resolution would fail even though Theorem 1 would stand. Minor typos (e.g., 'non-decreasing' where decreasing is meant in Lemma 4.3, and a loose constant 2/3 in the transitive part of Theorem 4) do not affect the main conclusions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a spectral-optimization method for reversible finite-state Markov chains and uses it to prove new quantitative relations between the L∞ mixing time, maximal hitting time, relaxation time, and higher-order spectral quantities. Theorem 1 gives t_mix^(∞)(ε) ≤ t_rel max{1, log(max_x t_{π→x}/(ε t_rel))}, hence t_mix^(∞) ≲ t_rel log(1 + t_hit/t_rel), and Corollary 1.1 characterizes when uniform mixing times and maximal hitting times are of the same order in terms of t_rel versus t_hit. Theorem 2 extends the method to higher ℓ and to average/pointwise L2 mixing times. Theorems 3 and 4 interpret these bounds through branching random walks whose particle number grows at rate of the spectral gap, with transitive chains giving a connection between intersection times of two BRWs and the L∞ mixing time. The paper further claims that this resolves Aldous and Fill's Open Problem 14.12 on mean-field coalescence, with the heavy lifting attributed to Oliveira [20].","tokens_in":24984,"tokens_out":21596,"duration_ms":195772,"significance":"If the results stand, Theorem 1 is a strong parameter-free improvement over the classical bounds (1.4), and Corollary 1.1 is a clean spectral characterization of the comparison t_mix^(∞) ≍ t_hit versus t_rel ≍ t_hit. The spectral-optimization proof is novel and appears to be complete; the BRW interpretation is a genuine probabilistic consequence rather than a restatement of the inequalities. The constants are universal and no fitted parameters appear. The main caveat is that the headline 'resolves the Aldous–Fill conjecture' is conditional on Oliveira [20], which the paper does not re-derive. In addition, Theorem 4 contains a displayed inequality with a factor error that must be corrected before publication; the qualitative '≲' form of the transitive statement remains correct after the fix.","major_comments":[{"comment":"The displayed inequality t_mix^(∞) ≤ t_rel max{1, (1/2) log(4Q/t_rel^2)} is false as stated. For the rate-1 reversible walk on the complete graph K_n, t_rel ≈ 1, Q ≈ n, and with the paper's convention t_mix^(∞) = t_mix^(∞)(1/2) we have t_mix^(∞) ≈ log(2n), whereas the right-hand side is about (1/2)log(4n); for large n the inequality fails by a factor of roughly 2 in the leading logarithm. The sentence 'the inequality is immediate from (1.6)' is consistent with the correct bound t_mix^(∞)(1/2) ≤ t_rel max{2, log(2Q/t_rel^2)}, or equivalently the bound t_mix^(∞)(1/4) ≤ t_rel max{2, log(4Q/t_rel^2)} already stated in §1.1. Please correct (1.16) and its proof; the later qualitative estimate t_mix^(∞) ≲ t_rel log(1 + √Q/t_rel) is not affected.","section":"§1.2, Eq. (1.16)"}],"minor_comments":[{"comment":"The sentence 'However, Theorem 3 asserts that this condition is in fact equivalent to the condition t_rel^(n) ≪ t_hit^(n)' is a cross-reference error: Theorem 3 concerns branching random walk hitting times, not the equivalence t_TV_mix ≪ t_hit ⇔ t_rel ≪ t_hit. That equivalence is Corollary 1.1 together with (2.4). Similarly, §1.1 refers to 'Theorem 3 (namely (1.16))', but (1.16) appears in Theorem 4.","section":"§1, p. 6"},{"comment":"The proof states that H_s(x,x) is non-decreasing in s; earlier in the paper and by spectral theory it is decreasing. The subsequent integral comparison is still valid, but the monotonicity statement should be corrected to avoid confusing readers.","section":"Lemma 4.3 proof"},{"comment":"The chain 't_rel ≤ √Q ≲ ∑_x π(x)ρ_x ≤ ρ_max' is dimensionally inconsistent and is not what the proof needs. The needed inequality is t_rel^2 ≤ Q ≲ ∑_x π(x)ρ_x ≤ ρ_max, which follows from (1.9)–(1.10). Please fix this display.","section":"Lemma 4.3 proof"},{"comment":"The proof of (4.11) asserts that P_{π,π}[τ_I > j(2E_{π,π}[τ_I] + t_mix^(∞)(1/4))] decays exponentially in j and says the details are routine. Since this exponential decay is used to obtain E_{π,π}[τ_I^2] ≲ (E_{π,π}[τ_I])^2, a short justification should be included.","section":"Transitive part of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The central spectral-optimization inequalities appear sound, and the method is likely to be useful beyond this paper. The Aldous–Fill resolution depends explicitly on Oliveira [20]; I would ask the authors to state this dependence prominently, especially because the introduction currently misattributes the key equivalence to Theorem 3. The main required technical correction is the factor error in (1.16); once that display is fixed and the cross-references are cleaned up, the paper should be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result, not a repackaging. The new inequality t_mix^∞(ε) ≤ trel max{1, log(max_x tπ→x/(ε trel))} and Corollary 1.1 are proved in full; the spectral optimization argument is fresh and the proof of Theorem 2 holds up on inspection. The paper's value is in giving a sharp, parameter-free relation between trel, thit, and t_mix^∞, and it genuinely closes the equivalence that the Aldous–Fill conjecture needed.\n\nWhat is new: the ℓ=1 bound and its corollary are new, as is the higher-order ℓ≥2 family (Theorem 2), the sharp torus example, and the branching random walk interpretation. The proof is honest: no fitted constants, no circular stepping. The case analysis in Theorem 2 rules out non-extremal configurations, and the spectral identities used are standard. I did not find a load-bearing gap.\n\nSoft spots: the headline resolution of Aldous–Fill is explicitly built on Oliveira [20]. If Oliveira's theorem had a gap or different hypotheses, the conjecture resolution would fail even though Theorem 1 stands. That is a normal division of labor, but the referee should check the exact statement in [20] and verify the chain conventions. The paper should also label the equivalence more carefully: in the introduction, the sentence saying 'Theorem 3 asserts that this condition is equivalent' is wrong as printed, since Theorem 3 concerns BRW hitting times; it should point to Corollary 1.1 or Theorem 1. Minor presentational issues: the derivation of (4.11) is omitted as routine, and in Lemma 4.3 H_s(x,x) is called non-decreasing when it should be decreasing. Neither affects the main conclusions.\n\nBottom line: the central argument holds, and the paper deserves a serious referee. I would accept after minor revisions. It is worth reading and citing if you work on mixing times, hitting times, or coalescing random walks.","headline":"Sharp spectral inequality relating mixing and hitting times, with a proof that holds up; the Aldous–Fill resolution is real but rests on Oliveira as advertised.","tokens_in":25583,"tokens_out":2583,"would_cite":true,"duration_ms":24263,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","60J27","60J80","60K35","05C81"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a quantitative inequality showing that a reversible chain's uniform mixing time is at most its relaxation time times the logarithm of the ratio of hitting to relaxation time, and uses it to resolve the Aldous–Fill…","keywords":["mixing times","hitting times","spectral optimization","branching random walk","intersection times","spectral gap","vertex-transitive graphs","coalescing random walk"],"falsifier":"A concrete refutation would be a finite irreducible reversible chain whose exact diagonalization gives $t_{\\mathrm{mix}}^{(\\infty)}(1/2) > t_{\\mathrm{rel}}\\max\\{1,\\log(2\\max_x t_{\\pi \\to x}/t_{\\mathrm{rel}})\\}$; searching small birth-and-death chains by exact computation is the direct test of Theorem 1.","tokens_in":24481,"feed_emoji":"🔄","tokens_out":13958,"duration_ms":124783,"temperature":0.7,"pith_summary":"For any finite reversible Markov chain, the paper bounds the uniform ($L_\\infty$) mixing time in terms of two more basic quantities: the relaxation time $t_{\\mathrm{rel}} = 1/\\mathrm{gap}$ and the maximal expected hitting time of a state $t_{\\mathrm{hit}}$. The main inequality, $t_{\\mathrm{mix}}^{(\\infty)} \\le C t_{\\mathrm{rel}}\\log(1 + t_{\\mathrm{hit}}/t_{\\mathrm{rel}})$, combined with the classical reverse direction, characterizes exactly when uniform mixing and hitting times separate. This completes a proof, begun in an earlier theorem cited in the paper, that under vertex-transitivity the spectral condition $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$ forces mean-field behavior for coalescing random walks. The same method yields higher-order versions and a branching-random-walk reading: the maximal expected hitting time, and under transitivity the expected intersection time, of a branching random walk whose particles split at rate $\\mathrm{gap}$, are comparable to the same logarithmic quantities.","feed_headline":"Spectral inequality decides when mixing beats hitting","feed_subtitle":"For reversible chains the two scales separate exactly when spectral gap times hitting time diverges.","key_machinery":"The engine is a 'spectral optimization' principle. The $L_\\infty$ mixing time is controlled by a sum of exponentials $\\sum_i e^{-\\lambda_i t}$ involving the eigenvalues $\\lambda_i$ of $I - P$, while the expected hitting time $t_{\\pi \\to x}$ and the average hitting time $t_\\odot$ are the same spectral sums with $1/\\lambda_i$ weights. The paper maximizes the exponential sum subject to the constraint that the weighted sum of $1/\\beta_i^\\ell$ is held fixed, and proves that the maximum is attained by concentrating all spectral weight at the smallest eigenvalue $\\lambda_2 = \\mathrm{gap}$, with the remaining weights sent to $\\infty$. The key monotonicity fact is that $x^\\ell e^{-2xt}$ decreases for $x \\ge 1/(2t)$ when $t \\ge \\ell t_{\\mathrm{rel}}/2$, so replacing any larger $\\beta_i$ by mass at $\\lambda_2$ preserves the constraint and only increases the objective. This reduces a mixing-time estimate to evaluating one exponential, and generalizes to $\\ell$-th order quantities $Q_\\ell = \\sum_{i \\ge 2} \\lambda_i^{-\\ell}$ and $\\sigma_{x,\\ell}$, yielding the higher-order and intersection-time bounds.","core_discovery":"The central discovery is Theorem 1: for every irreducible reversible Markov chain on a finite state space and every $\\varepsilon > 0$, $t_{\\mathrm{mix}}^{(\\infty)}(\\varepsilon) \\le t_{\\mathrm{rel}}\\max\\{1,\\log(\\max_x t_{\\pi \\to x}/(\\varepsilon t_{\\mathrm{rel}}))\\}$, and in particular $t_{\\mathrm{mix}}^{(\\infty)} \\lesssim t_{\\mathrm{rel}}\\log(1 + t_{\\mathrm{hit}}/t_{\\mathrm{rel}})$. Because the classical bound $t_{\\mathrm{mix}}^{(\\infty)} \\ge t_{\\mathrm{rel}}\\log 2$ goes in the opposite direction, the paper obtains a two-sided spectral characterization: a sequence of finite reversible chains has uniform mixing time of strictly smaller order than the maximal hitting time if and only if the relaxation time is of strictly smaller order than the hitting time, with the analogous equivalence for constancy up to factors. The paper then combines this with an earlier theorem, quoted as [20], that on vertex-transitive graphs total-variation mixing time much smaller than hitting time already implies mean-field coalescence, thereby resolving the Aldous–Fill conjecture (Open Problem 14.12). In the same framework, the expected hitting time of a critical branching random walk—where each particle splits at rate $\\mathrm{gap}$—is shown to be comparable to $t_{\\mathrm{rel}}\\log(1 + t_{\\mathrm{hit}}/t_{\\mathrm{rel}})$, and in the transitive case the expected intersection time of two such walks is comparable to $t_{\\mathrm{rel}}\\log(1 + \\sqrt{Q}/t_{\\mathrm{rel}})$.","pith_inferences":["The spectral-optimization mechanism is not tied to $\\ell = 1$; it suggests that for $\\ell \\ge 3$ the quantities $Q_\\ell = \\sum_{i \\ge 2} \\lambda_i^{-\\ell}$ may admit probabilistic interpretations as multi-particle intersection times, which the paper leaves open.","If the method extends to infinite reversible chains with spectral radius $\\rho$ replacing the spectral gap, the branching-random-walk picture would give a natural critical-branching criterion for mixing behavior on infinite graphs.","A practical consequence of the branching-random-walk bounds is a Monte-Carlo route to mixing-time estimates: simulate two branching random walks with splitting rate $\\mathrm{gap}$, estimate their intersection time, and read off $t_{\\mathrm{rel}}\\log(1 + \\sqrt{Q}/t_{\\mathrm{rel}})$, without computing eigenvalues.","The equivalence $t_{\\mathrm{mix}}^{(\\infty)} \\ll t_{\\mathrm{hit}} \\iff t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$ suggests that families of graphs with few small Laplacian eigenvalues generically have mixing time of smaller order than hitting time, because the spectral-optimization worst case requires mass concentration near the edge of the spectrum."],"forward_implications":["For a sequence of reversible finite-state chains, $t_{\\mathrm{mix}}^{(\\infty)} \\ll t_{\\mathrm{hit}}$ holds if and only if $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$, so the spectral-gap–hitting-time product is a complete criterion for separation of the two time scales.","The Aldous–Fill conjecture holds: on vertex-transitive graphs, $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$ implies that the coalescence time of coalescing random walks, rescaled by the meeting time, converges to the Kingman-coalescent law.","A branching random walk in which each particle splits at rate $\\mathrm{gap}$ has maximal expected hitting time comparable to $t_{\\mathrm{rel}}\\log(1 + t_{\\mathrm{hit}}/t_{\\mathrm{rel}})$, and under transitivity its expected intersection time is comparable to $t_{\\mathrm{rel}}\\log(1 + \\sqrt{Q}/t_{\\mathrm{rel}})$, refining earlier intersection-mixing bounds.","The condition $t_{\\mathrm{mix}}^{\\mathrm{TV}} \\ll t_{\\mathrm{hit}}$, and its $L_\\infty$ analogue, is stable under rough isometries and small edge-weight perturbations, because both are equivalent to the robust spectral condition $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$.","Higher-order versions recover sharp mixing-time estimates on tori: for the $d$-dimensional torus, $t_{\\mathrm{mix}}^{(\\infty)}(\\mathbb{Z}_m^d) = O(d\\,t_{\\mathrm{rel}})$, matching the true order up to a dimension-dependent constant."],"supporting_citations":[{"why":"Formulates the Aldous–Fill conjecture (Open Problem 14.12) and supplies the eigentime identities relating hitting times to spectral sums that the proof uses.","marker":"[5]"},{"why":"Provides the standard hierarchy of mixing-time and hitting-time bounds, the spectral decomposition formulas, and the separation and total-variation relations used throughout the arguments.","marker":"[18]"},{"why":"Carries the main load for the conjecture: proves that total-variation mixing time much smaller than hitting time implies mean-field coalescence on vertex-transitive graphs, the condition that the new equivalence upgrades to $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$.","marker":"[20]"},{"why":"Establishes the first intersection-time–mixing-time relations and the bound $E_{\\pi,\\pi}[\\tau_I] \\asymp \\sqrt{Q}$ in the transitive setup that Theorem 4 refines.","marker":"[24]"},{"why":"Supplies the coupling and mixture argument used inside the proof of the upper bound on branching-random-walk hitting times.","marker":"[22]"}],"fun_headline_variants":["Mixing beats hitting iff spectral-gap times hitting diverges","Aldous–Fill conjecture resolved via spectral-gap inequality","Critical branching random walks probe mixing time up to constant","Spectral gap decides when mixing is faster than hitting","Two-sided spectral bound: mixing and hitting separate exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the earlier theorem quoted as [20] is correct: on vertex-transitive graphs, total-variation mixing much smaller than hitting already forces mean-field coalescence, with the new paper supplying the equivalence that turns the spectral condition into that mixing-time condition.","fun_headline_variants_meta":{"raw":{"variants":["Mixing beats hitting iff spectral-gap times hitting diverges","Aldous–Fill conjecture resolved via spectral-gap inequality","Critical branching random walks probe mixing time up to constant","Spectral gap decides when mixing is faster than hitting","Two-sided spectral bound: mixing and hitting separate exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000339,"raw_usage":{"total_tokens":1973,"prompt_tokens":1148,"completion_tokens":825,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":764,"completion_tokens_details":{"reasoning_tokens":746}},"tokens_in":764,"tokens_out":825,"duration_ms":8481,"temperature":1.0,"reasoning_tokens":746,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:36:35.108910+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete refutation would be a finite irreducible reversible chain whose exact diagonalization gives $t_{\\mathrm{mix}}^{(\\infty)}(1/2) > t_{\\mathrm{rel}}\\max\\{1,\\log(2\\max_x t_{\\pi \\to x}/t_{\\mathrm{rel}})\\}$; searching small birth-and-death chains by exact computation is the direct test of Theorem 1.","supporting_citations":[{"cited_title":"Unfinished manuscript","cited_arxiv_id":null,"evidence_quote":"Formulates the Aldous–Fill conjecture (Open Problem 14.12) and supplies the eigentime identities relating hitting times to spectral sums that the proof uses."},{"cited_title":"Markov chains and mixing times","cited_arxiv_id":null,"evidence_quote":"Provides the standard hierarchy of mixing-time and hitting-time bounds, the spectral decomposition formulas, and the separation and total-variation relations used throughout the arguments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Carries the main load for the conjecture: proves that total-variation mixing time much smaller than hitting time implies mean-field coalescence on vertex-transitive graphs, the condition that the new equivalence upgrades to $t_{\\mathrm{rel}} \\ll t_{\\mathrm{hit}}$."},{"cited_title":"Electron","cited_arxiv_id":null,"evidence_quote":"Establishes the first intersection-time–mixing-time relations and the bound $E_{\\pi,\\pi}[\\tau_I] \\asymp \\sqrt{Q}$ in the transitive setup that Theorem 4 refines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the coupling and mixture argument used inside the proof of the upper bound on branching-random-walk hitting times."}],"review_version":1}