pith. sign in

arxiv: 2605.17513 · v1 · pith:OLCEGV2Knew · submitted 2026-05-17 · 🧮 math.PR

Nonconcentration of hitting times for random walks on graphs

Rafael Chiclana This is my paper

Pith reviewed 2026-05-19 22:37 UTC · model grok-4.3

classification 🧮 math.PR
keywords random walkshitting timesvariance boundsgraphsconcentration inequalitiesMarkov chainstrees
4
0 comments X

The pith

Hitting times of random walks on graphs have variance at least the square of their mean divided by one plus the log of the number of vertices.

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

The paper proves a non-concentration result for hitting times of simple random walks on finite connected graphs. It establishes that for any such graph with n vertices the variance of the hitting time plus its expectation is at least the square of the expectation divided by one plus log n. The logarithmic factor is shown to be sharp up to constants through explicit constructions. Under a bounded-degree assumption the additive term drops away, leaving a variance lower bound that depends only on the mean hitting time and the graph distance between the starting point and target.

Core claim

For every connected graph with n vertices, Var_x(τ_y) + E_x τ_y ≥ (E_x τ_y)^2 / (1 + log n). Under bounded degree the additive mean term can be removed to obtain a variance lower bound depending only on E_x τ_y and dist(x,y). High-degree graphs exist where the mean hitting time is linear in n while the variance stays bounded; the same graphs disprove the Norris-Peres-Zhai conjecture on local nonconcentration. A sharper estimate holds on trees, the argument extends to finite reversible Markov chains, and Holroyd's interval conjecture fails even on bounded-degree trees.

What carries the argument

A lower bound on Var_x(τ_y) + E_x τ_y in terms of (E_x τ_y)^2 and log n, obtained by analyzing the simple symmetric random walk on an undirected connected finite graph.

If this is right

  • The logarithmic factor in the denominator is optimal up to constant factors on general graphs.
  • On bounded-degree graphs the variance is bounded below by a quantity depending only on the mean hitting time and the graph distance.
  • The Norris-Peres-Zhai conjecture on local nonconcentration of hitting times is false.
  • Holroyd's interval conjecture fails even for bounded-degree trees.
  • The variance-mean inequality extends to finite reversible Markov chains.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The nonconcentration suggests that cover times or search times on large networks are governed by a wider spread of hitting times than previously expected.
  • Comparing simulations on bounded-degree expanders against high-degree star-like graphs would isolate the precise effect of maximum degree on variance.
  • The failure of the interval conjecture on trees indicates that hitting-time distributions on acyclic graphs require models that allow larger fluctuations than interval-type assumptions permit.

Load-bearing premise

The random walk is the simple symmetric random walk on an undirected connected finite graph, and the sharpness constructions rely on specific high-degree vertex placements that keep variance bounded while making the mean linear.

What would settle it

A connected graph on n vertices together with vertices x and y for which Var_x(τ_y) + E_x τ_y falls below (E_x τ_y)^2 / (1 + log n) for arbitrarily large n would falsify the central inequality.

Figures

Figures reproduced from arXiv: 2605.17513 by Rafael Chiclana.

Figure 1
Figure 1. Figure 1: for the case L = 3 and B = 2. The level process is a birth-death chain on {0, 1, . . . , L, L + 1}, where L + 1 corresponds to y. From 0, the walk moves to 1 deterministically. For 1 ≤ i ≤ L − 1, it moves to i + 1 with probability p := B B + 1 and to i − 1 with probability q := 1 B + 1 . From L, it moves to L + 1 with probability 1/2, and to L − 1 with probability 1/2. Let T0 be the hitting time of level L… view at source ↗
read the original abstract

We study nonconcentration of hitting times for simple random walk on finite graphs. We prove that, for every connected graph with $n$ vertices, \[ \operatorname{Var}_x(\tau_y)+\mathbb E_x\tau_y \ge \frac{(\mathbb E_x\tau_y)^2}{1+\log n}, \] with the logarithmic term sharp up to constants. Under a bounded-degree assumption the additive mean term can be removed, giving a variance lower bound depending only on \(\mathbb E_x\tau_y\) and the graph distance \(\dist(x,y)\). We show that this degree assumption is necessary by constructing high-degree graphs with linear mean and bounded variance; the same construction disproves a conjecture of Norris-Peres-Zhai concerning local nonconcentration of hitting times. We also prove a sharper tree estimate, extend the main argument to finite reversible Markov chains, and show that Holroyd's interval conjecture, stated in Norris-Peres-Zhai, fails even for bounded-degree trees.

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.

Referee Report

2 major / 2 minor

Summary. The paper proves that for simple symmetric random walk on any connected undirected finite graph with n vertices, Var_x(τ_y) + E_x τ_y ≥ (E_x τ_y)^2 / (1 + log n), with the log n factor sharp up to constants. Under a bounded-degree hypothesis the additive term is removable, yielding a variance lower bound depending only on the mean and dist(x,y). High-degree graph constructions are used to establish sharpness, to show the degree hypothesis is necessary, and to disprove the Norris-Peres-Zhai local nonconcentration conjecture. The paper also gives a sharper estimate on trees, extends the argument to finite reversible Markov chains, and shows that Holroyd's interval conjecture fails even on bounded-degree trees.

Significance. If the claims hold, the work supplies a clean, sharp non-concentration result for hitting times that separates the general-graph case from the bounded-degree case and supplies explicit counterexamples to two existing conjectures. The reliance on standard reversible-chain tools (Green-function or electrical-network estimates) together with concrete constructions makes the contribution technically solid and potentially useful for further work on mixing and hitting times.

major comments (2)
  1. [§4] §4 (high-degree constructions): the claim that these graphs achieve E_x τ_y = Θ(n) while keeping Var_x(τ_y) = O(1) is load-bearing for both the sharpness statement and the disproof of the Norris-Peres-Zhai conjecture. The second-moment analysis must explicitly control the contribution of long excursions after leaving the high-degree hubs; if return probabilities or escape times allow heavy tails, the variance bound fails and the constructions no longer separate the bounded-degree case.
  2. [Markov-chain extension] The extension to finite reversible Markov chains (stated after the graph results) inherits the same second-moment closure issue at high-degree states; the manuscript should verify that the Green-function estimates used for the graph case carry over without additional assumptions on the stationary measure.
minor comments (2)
  1. [Abstract] The abstract and introduction should state the precise definition of τ_y (first hitting time) and clarify whether the results are for fixed x,y or hold uniformly.
  2. [Tree estimate] Notation for the logarithmic factor (1 + log n) should be compared explicitly with the tree estimate to highlight the improvement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and indicate the revisions we will make to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (high-degree constructions): the claim that these graphs achieve E_x τ_y = Θ(n) while keeping Var_x(τ_y) = O(1) is load-bearing for both the sharpness statement and the disproof of the Norris-Peres-Zhai conjecture. The second-moment analysis must explicitly control the contribution of long excursions after leaving the high-degree hubs; if return probabilities or escape times allow heavy tails, the variance bound fails and the constructions no longer separate the bounded-degree case.

    Authors: We agree that explicit control of second-moment contributions from excursions is essential. Our high-degree constructions consist of a small clique of hubs with attached paths or trees of bounded degree. Upon leaving a hub, the walk enters an attached component from which the return probability to the hub is bounded below by a positive constant (proportional to the hub degree), yielding geometrically decaying tails for excursion lengths. Consequently, the second-moment contribution of any single excursion is O(1), and the total variance remains O(1) while the mean hitting time is Θ(n). To address the concern directly, we will add a short lemma in §4 that bounds the moment-generating function of excursion times via standard gambler's-ruin estimates on the attached trees, confirming that heavy tails do not arise. revision: partial

  2. Referee: [Markov-chain extension] The extension to finite reversible Markov chains (stated after the graph results) inherits the same second-moment closure issue at high-degree states; the manuscript should verify that the Green-function estimates used for the graph case carry over without additional assumptions on the stationary measure.

    Authors: The Green-function and electrical-network identities we employ are valid for any finite reversible Markov chain and depend only on reversibility together with the associated Dirichlet form; they require no bounded-degree hypothesis and impose no further restrictions on the stationary measure beyond the standard normalization. The high-degree states are treated via effective resistances exactly as in the graph setting. We will insert a brief clarifying paragraph immediately after the statement of the Markov-chain theorem, noting that the proofs transfer verbatim with no additional assumptions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard techniques and explicit constructions

full rationale

The central inequality follows from reversible Markov chain methods (Green function estimates and electrical networks) that are independent of the target variance bound. Sharpness and the necessity of the bounded-degree hypothesis are established by explicit high-degree graph constructions that directly control return probabilities and escape times. These steps rely on counting arguments and probabilistic estimates rather than any fitted parameter renamed as a prediction, self-definitional relation, or load-bearing self-citation. The paper is self-contained against external benchmarks with no reduction of the claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard definitions of hitting times and simple random walks without introducing new free parameters or postulated entities; all bounds are derived from graph structure and Markov properties.

axioms (1)
  • standard math Hitting times are well-defined for simple random walks on finite connected undirected graphs
    Invoked throughout the statements of the main inequality and extensions to Markov chains.

pith-pipeline@v0.9.0 · 5687 in / 1252 out tokens · 32641 ms · 2026-05-19T22:37:18.247183+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages

  1. [1]

    Random walks on the ran- dom graph.The Annals of Probability, 46(1):456–490, 2018.doi:doi:10.1214/17-AOP1189

    Berestycki, Nathana\". Random walks on the random graph , JOURNAL =. 2018 , NUMBER =. doi:10.1214/17-AOP1189 , URL =

    work page doi:10.1214/17-aop1189 2018

  2. [2]

    Cutoff phenomena for random walks on random regular graphs

    Lubetzky, Eyal and Sly, Allan , TITLE =. Duke Math. J. , FJOURNAL =. 2010 , NUMBER =. doi:10.1215/00127094-2010-029 , URL =

    work page doi:10.1215/00127094-2010-029 2010

  3. [3]

    arXiv preprint arXiv:2012.11484 , year=

    Cutoff on trees is rare , author=. arXiv preprint arXiv:2012.11484 , year=

    work page arXiv 2012

  4. [4]

    Coupling from the past

    Levin, David A. and Peres, Yuval , TITLE =. 2017 , PAGES =. doi:10.1090/mbk/107 , URL =

    work page doi:10.1090/mbk/107 2017

  5. [5]

    Chen, Guan-Yu and Saloff-Coste, Laurent , TITLE =. J. Appl. Probab. , FJOURNAL =. 2013 , NUMBER =. doi:10.1239/jap/1389370092 , URL =

    work page doi:10.1239/jap/1389370092 2013

  6. [6]

    Peres, Yuval and Sousi, Perla , TITLE =. Ann. Fac. Sci. Toulouse Math. (6) , FJOURNAL =. 2015 , NUMBER =. doi:10.5802/afst.1463 , URL =

    work page doi:10.5802/afst.1463 2015

  7. [7]

    Diaconis, Persi and Shahshahani, Mehrdad , TITLE =. Z. Wahrsch. Verw. Gebiete , FJOURNAL =. 1981 , NUMBER =. doi:10.1007/BF00535487 , URL =

    work page doi:10.1007/bf00535487 1981

  8. [8]

    Aldous, David and Diaconis, Persi , TITLE =. Amer. Math. Monthly , FJOURNAL =. 1986 , NUMBER =. doi:10.2307/2323590 , URL =

    work page doi:10.2307/2323590 1986

  9. [9]

    Basu, Riddhipratim and Hermon, Jonathan and Peres, Yuval , TITLE =. Ann. Probab. , FJOURNAL =. 2017 , NUMBER =. doi:10.1214/16-AOP1090 , URL =

    work page doi:10.1214/16-aop1090 2017

  10. [10]

    Peres, Yuval and Sousi, Perla , TITLE =. J. Theoret. Probab. , FJOURNAL =. 2015 , NUMBER =. doi:10.1007/s10959-013-0497-9 , URL =

    work page doi:10.1007/s10959-013-0497-9 2015

  11. [11]

    Ben-Hamou, Anna and Lubetzky, Eyal and Peres, Yuval , TITLE =. Ann. Inst. Henri Poincar\'. 2019 , NUMBER =. doi:10.1214/18-aihp911 , URL =

    work page doi:10.1214/18-aihp911 2019

  12. [12]

    , TITLE =

    Addario-Berry, Louigi and Roberts, Matthew I. , TITLE =. J. Stat. Phys. , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s10955-017-1917-5 , URL =

    work page doi:10.1007/s10955-017-1917-5 2018

  13. [13]

    Diaconis and L

    Diaconis, P. and Saloff-Coste, L. , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 1996 , NUMBER =. doi:10.1214/aoap/1034968224 , URL =

    work page doi:10.1214/aoap/1034968224 1996

  14. [14]

    Electron

    Ding, Jian and Peres, Yuval , TITLE =. Electron. Commun. Probab. , FJOURNAL =. 2013 , PAGES =. doi:10.1214/ECP.v18-2765 , URL =

    work page doi:10.1214/ecp.v18-2765 2013

  15. [15]

    Hermon, Jonathan and Peres, Yuval , TITLE =. Probab. Theory Related Fields , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s00440-017-0769-x , URL =

    work page doi:10.1007/s00440-017-0769-x 2018

  16. [16]

    Fill, James Allen , TITLE =. J. Theoret. Probab. , FJOURNAL =. 2009 , NUMBER =. doi:10.1007/s10959-009-0235-5 , URL =

    work page doi:10.1007/s10959-009-0235-5 2009

  17. [17]

    Pacific J

    Karlin, Samuel and McGregor, James , TITLE =. Pacific J. Math. , FJOURNAL =. 1959 , PAGES =

    work page 1959

  18. [18]

    1979 , PAGES =

    Keilson, Julian , TITLE =. 1979 , PAGES =

    work page 1979

  19. [19]

    , TITLE =

    Halmos, Paul R. , TITLE =. 1974 , PAGES =

    work page 1974

  20. [20]

    Gurel-Gurevich, Ori and Nachmias, Asaf , TITLE =. Ann. Probab. , FJOURNAL =. 2013 , NUMBER =. doi:10.1214/12-AOP785 , URL =

    work page doi:10.1214/12-aop785 2013

  21. [21]

    Norris, James and Peres, Yuval and Zhai, Alex , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2017 , NUMBER =. doi:10.1017/S0963548317000074 , URL =

    work page doi:10.1017/s0963548317000074 2017

  22. [22]

    and Brown, Mark , TITLE =

    Aldous, David J. and Brown, Mark , TITLE =. Stochastic inequalities (. 1992 , MRCLASS =. doi:10.1214/lnms/1215461937 , URL =

    work page doi:10.1214/lnms/1215461937 1992

  23. [23]

    , TITLE =

    Saumard, Adrien and Wellner, Jon A. , TITLE =. Stat. Surv. , FJOURNAL =. 2014 , PAGES =. doi:10.1214/14-SS107 , URL =

    work page doi:10.1214/14-ss107 2014

  24. [24]

    ESAIM Probab

    Miclo, Laurent , TITLE =. ESAIM Probab. Stat. , FJOURNAL =. 2010 , PAGES =. doi:10.1051/ps:2008037 , URL =

    work page doi:10.1051/ps:2008037 2010

  25. [25]

    Bobkov and Arnaud Marsiglietti and James Melbourne , Title =

    Sergey G. Bobkov and Arnaud Marsiglietti and James Melbourne , Title =. 2020 , Eprint =

    work page 2020

  26. [26]

    Electron

    Hermon, Jonathan and Peres, Yuval , TITLE =. Electron. J. Probab. , FJOURNAL =. 2018 , PAGES =. doi:10.1214/18-EJP154 , URL =

    work page doi:10.1214/18-ejp154 2018

  27. [27]

    , TITLE =

    Guruswami, Venkatesan and Kumar, Vinayak M. , TITLE =. 12th. 2021 , MRCLASS =

    work page 2021

  28. [28]

    Gillman, David , TITLE =. SIAM J. Comput. , FJOURNAL =. 1998 , NUMBER =. doi:10.1137/S0097539794268765 , URL =

    work page doi:10.1137/s0097539794268765 1998

  29. [29]

    Cohen, Gil and Peri, Noam and Ta-Shma, Amnon , TITLE =. S. [2021] 2021 , MRCLASS =. doi:10.1145/3406325.3451049 , URL =

    work page doi:10.1145/3406325.3451049 2021

  30. [30]

    Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon , TITLE =. 49th. 2022 , MRCLASS =. doi:10.4230/lipics.icalp.2022.43 , URL =

    work page doi:10.4230/lipics.icalp.2022.43 2022

  31. [31]

    and Peres, Yuval , TITLE =

    Penrose, Mathew D. and Peres, Yuval , TITLE =. Electron. J. Probab. , FJOURNAL =. 2011 , PAGES =. doi:10.1214/EJP.v16-968 , URL =

    work page doi:10.1214/ejp.v16-968 2011

  32. [32]

    Effective

    Kloeckner, Beno\^. Effective. Ann. Appl. Probab. , FJOURNAL =. 2019 , NUMBER =. doi:10.1214/18-AAP1438 , URL =

    work page doi:10.1214/18-aap1438 2019

  33. [33]

    37th Computational Complexity Conference (CCC 2022) , pages =

    Golowich, Louis and Vadhan, Salil , title =. 37th Computational Complexity Conference (CCC 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.CCC.2022.27 , annote =

    work page doi:10.4230/lipics.ccc.2022.27 2022

  34. [34]

    Hoory, Shlomo and Linial, Nathan and Wigderson, Avi , TITLE =. Bull. Amer. Math. Soc. (N.S.) , FJOURNAL =. 2006 , NUMBER =. doi:10.1090/S0273-0979-06-01126-8 , URL =

    work page doi:10.1090/s0273-0979-06-01126-8 2006

  35. [35]

    Zolotukhin, Anatolii and Nagaev, Sergei and Chebotarev, Vladimir , TITLE =. Mod. Stoch. Theory Appl. , FJOURNAL =. 2018 , NUMBER =. doi:10.15559/18-vmsta113 , URL =

    work page doi:10.15559/18-vmsta113 2018

  36. [36]

    , TITLE =

    Mann, Brad W. , TITLE =. 1996 , PAGES =

    work page 1996

  37. [37]

    Expander

    Vadhan, Salil , year =. Expander

    work page

  38. [38]

    2019 , PAGES =

    Durrett, Rick , TITLE =. 2019 , PAGES =. doi:10.1017/9781108591034 , URL =

    work page doi:10.1017/9781108591034 2019

  39. [39]

    2022 , Eprint =

    Louis Golowich , Title =. 2022 , Eprint =

    work page 2022

  40. [40]

    Kolmogorov, A. N. , TITLE =. Izvestiya Akad. Nauk SSSR. Ser. Mat. , FJOURNAL =. 1949 , PAGES =

    work page 1949

  41. [41]

    Nagaev, S. V. , TITLE =. Teor. Veroyatnost. i Primenen. , FJOURNAL =. 1957 , PAGES =

    work page 1957

  42. [42]

    Nagaev, S. V. , Title =. Theory Probab. Appl. , ISSN =. 1962 , Language =. doi:10.1137/1106005 , zbMATH =

    work page doi:10.1137/1106005 1962

  43. [43]

    2010 , PAGES =

    Helson, Henry , TITLE =. 2010 , PAGES =

    work page 2010

  44. [44]

    Nadtochiy, Sergey and Shkolnikov, Mykhaylo , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 2019 , NUMBER =. doi:10.1214/18-AAP1403 , URL =

    work page doi:10.1214/18-aap1403 2019

  45. [45]

    Methodol

    Avrachenkov, Konstantin and Piunovskiy, Alexey and Zhang, Yi , TITLE =. Methodol. Comput. Appl. Probab. , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s11009-017-9600-5 , URL =

    work page doi:10.1007/s11009-017-9600-5 2018

  46. [46]

    and McNicholas, Paul D

    Balka, Jeremy and Desmond, Anthony F. and McNicholas, Paul D. , TITLE =. Lifetime Data Anal. , FJOURNAL =. 2009 , NUMBER =. doi:10.1007/s10985-008-9108-y , URL =

    work page doi:10.1007/s10985-008-9108-y 2009

  47. [47]

    Perron, Oskar , TITLE =. Math. Ann. , FJOURNAL =. 1907 , NUMBER =. doi:10.1007/BF01449896 , URL =

    work page doi:10.1007/bf01449896 1907

  48. [48]

    Problems in analysis (

    Cheeger, Jeff , TITLE =. Problems in analysis (. 1970 , MRCLASS =

    work page 1970

  49. [49]

    , TITLE =

    Binder, Kurt and Heermann, Dieter W. , TITLE =. 2019 , PAGES =. doi:10.1007/978-3-030-10758-1 , URL =

    work page doi:10.1007/978-3-030-10758-1 2019

  50. [50]

    and Kroese, Dirk P

    Rubinstein, Reuven Y. and Kroese, Dirk P. , TITLE =. 2017 , PAGES =

    work page 2017

  51. [51]

    Longla, Martial and Peligrad, Costel and Peligrad, Magda , TITLE =. J. Appl. Probab. , FJOURNAL =. 2012 , NUMBER =. doi:10.1017/s0021900200012894 , URL =

    work page doi:10.1017/s0021900200012894 2012

  52. [52]

    Nagaev, S. V. , TITLE =. J. Math. Sci. (N.Y.) , FJOURNAL =. 2016 , NUMBER =. doi:10.1007/s10958-016-3023-7 , URL =

    work page doi:10.1007/s10958-016-3023-7 2016

  53. [53]

    Electron

    Chiclana, Rafael and Peres, Yuval , TITLE =. Electron. Commun. Probab. , FJOURNAL =. 2022 , PAGES =. doi:10.1214/22-ecp468 , URL =

    work page doi:10.1214/22-ecp468 2022

  54. [54]

    2022 , Eprint =

    Rafael Chiclana and Yuval Peres , Title =. 2022 , Eprint =

    work page 2022