REVIEW 2 major objections 3 minor 6 references
How fast does the range of simple random walk grow?
T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The paper proves a universal lower bound on random-walk range — (t/log t)^{1/3} on every graph — builds lollipop chains making this sharp, and advertises (but only conjectures) that vertex expansion forces linear range.
desk verdict The body is honest and mostly correct, but the abstract oversells it: the advertised vertex-isoperimetry theorem is only a conjecture in the text. 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 load-bearing inequality is Theorem 1: E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n-1} 1/g(r), where f(n) is the maximum edge count of an induced n-vertex subgraph and g(r) the minimum volume of a radius-r ball. The proof decomposes the walk into escape attempts: between the kth and (k+1)st discoveries the walk sits inside the set S_k of discovered vertices, and Lemma 2 bounds the escape time by roughly the edge count of S_k times the distance from the current vertex to the boundary. Lemma 3 then bounds the sum of those distances by a packing argument — discoveries more than 2r apart have disjoint r-balls, so there cannot be too many of them. The lollipop chain is the matching lower-bound mechanism: a cl
What would settle it
Compute, on an n-vertex lollipop (a clique of size n/2 with a path of length n/2 attached), the expected hitting time from an internal clique vertex to the path endpoint; if it grows slower than n^3, the sharpness claim fails. Alternatively, measure liminf_{t→∞} E_x R_t / t on any vertex-nonamenable graph with unbounded degrees; if it is 0 for some x, the advertised linear-range theorem is false.
Extended reading notes
Core claim
The central technical discovery is a bound on the discovery time T_n — the first time the walk has seen n distinct vertices — in terms of two coarse geometric parameters: f(n), the largest number of edges inside any n vertices, and g(r), the smallest size of a radius-r ball. The bound E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n-1} 1/g(r) yields the universal estimate E[T_n] ≤ 4 n^3 log n and the range lower bound E[R_t] ≥ c (t/log t)^{1/3}. A chain of lollipop graphs — cliques separated by long paths — is shown to have E[T_n] ≥ c n^3 for all dyadic n, so the universal estimate is sharp apart from the logarithm and the lower and upper logarithmic exponents of E[R_t] are both 1/3. The paper additionally prov
Load-bearing premise
The weakest load-bearing premise is the asserted chain — vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex — on which the advertised linear-range theorem rests; separately, the sharpness example rests on an unproved 'well-known' lower bound that the expected time from a lollipop clique to the path end is at least c n^3.
Editorial extensions
If this is right
- On every infinite connected locally finite graph, E[R_t] ≥ c (t/log t)^{1/3} for all t ≥ 2, so no graph can slow discovery to less than a sub-polynomial rate.
- The expected nth discovery time is at most 4 n^3 log n universally; when the minimum ball size grows like r^{1+δ}, the logarithmic factor disappears and E[T_n] = O(n^3).
- There exists a single infinite graph for which E[T_n] ≥ c n^3 at every dyadic scale, so the polynomial n^3 in the universal bound is best possible up to the logarithmic factor.
- The paper's advertised result — that positive vertex expansion forces linear expected range — would imply that every vertex-nonamenable graph has E_x R_t ≥ c(G)(t+1) for every start x, even when degrees are unbounded.
- In finite n-vertex vertex expanders, the expected hitting time of an independent stationary random target is Θ(n), with no restriction on degrees.
Reading between the lines
- The gap between the abstract's advertised theorem and the body's Conjecture 1 suggests that the decisive missing ingredient is a proof that vertex expansion yields a uniform positive escape probability on unbounded-degree graphs; if such a proof is found, the linear-range claim would follow without any degree control.
- The lollipop chain answers one oscillation question narrowly: a graph can have subdiffusive plateaus without superdiffusive bursts, since both logarithmic exponents equal 1/3. The broader question — whether any α < 1/2 forces β > 1/2 — remains open and could be tested by constructing graphs with α = 1/3 and β < 1.
- The escape-time lemma suggests a diagnostic: slow range growth implies large local-time concentration. A natural extension would be a converse statement — that large local-time peaks force sublinear expected range — which the paper does not address.
- The finite-expander hitting-time result is a finite analogue of the linear-range conjecture; proving a matching escape-probability estimate for unbounded-degree vertex expanders would likely settle Conjecture 1.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the growth of the expected range E[R_t] and the discovery times T_n of simple random walk on infinite, connected, locally finite graphs. The core technical result is Theorem 1: E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n−1} 1/g(r), where f(n) is the maximal edge count of an n-vertex induced subgraph and g(r) the minimal ball size. This yields universal bounds E[T_n] ≤ 4 n^3 log n and E[R_t] ≥ c(t/log t)^{1/3}. The authors construct a multi-scale lollipop graph showing E[T_n] ≥ c n^3 at dyadic scales, and prove a low-tech linear-range estimate from uniform transience. The abstract additionally claims a main theorem — positive vertex isoperimetry implies linear expected range without bounded-degree assumptions — but the body only states this as Conjecture 1. Similar advertised results in the abstract (finite expander hitting time Θ(n), a mixing-time statement) are not present in the body.
Significance. If the body's Theorem 1 and Proposition 1 are correct — and I found no error in the proof of Theorem 1 or the packing argument — the paper provides a clean, parameter-free coarse-geometric bound that is close to optimal in the worst case. The construction of a single graph with matching lower bounds at dyadic scales is valuable, and the proof is elementary and self-contained apart from the standard lollipop estimate. However, the headline result announced in the abstract is not established in the submitted text. As written, the paper's actual contribution is the universal bound and the lollipop sharpness example, plus Proposition 2 and Conjecture 1. The manuscript needs either to prove the missing theorem or to revise the abstract so that it matches the body.
major comments (2)
- [Abstract / §4] The abstract announces as proven: if ι_V(G)>0 then E_x R_t ≥ c(G)(t+1) with no bounded-degree assumption, via 'vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex.' In §4 the only statement of this implication is Conjecture 1; no proposition, proof, or derivation of the Dirichlet-inequality step is supplied. The advertised finite counterpart (expected hitting time of an independent stationary random target in a finite vertex expander is Θ(n)) and the closing mixing-time statement also do not appear in the body. This mismatch is load-bearing: the abstract's main result is not recoverable from the proved results. Please add the proofs or rewrite the abstract to present the proved results as the actual content.
- [§3, Proposition 1] The sharpness claim rests entirely on the assertion that the expected hitting time of the end of a lollipop from the clique is at least c n^3, stated as 'well known (and easily seen)' with references [2,3,4]. Since Proposition 1 is the only evidence for essential optimality of Corollary 1, this estimate should be stated precisely as a lemma and proved or quoted with exact hypotheses. The references are standard, but the current text leaves the load-bearing external input unstated, making it impossible for the reader to verify the exponent without going to the literature.
minor comments (3)
- [Corollary 2, proof] After invoking Markov's inequality, the display should read ≤ 4n^3 log n/(t+1), not equality. The constant C in the choice of n is also never explicitly defined; please make it concrete.
- [Abstract / body] The abstract says 'we move our elementary proof of the weaker bound to a later section' and 'we close with a related bounded-degree mixing statement'; neither description matches the body, where the proof of the weaker bound appears in §2 and no mixing statement appears. Please synchronize the abstract with the submitted version.
- [§3, Proposition 1] In the multi-scale construction, the indices n_i are chosen as 2^i, and the graph then satisfies the lower bound at dyadic scales. It would be helpful to explicitly state that the lower bound at scale n is for the discovery time T_n (not for the range at time n), as the notation E[T_n] already indicates.
Circularity Check
No circular step found; the abstract/body mismatch is a missing-proof issue, not a reduction to inputs.
full rationale
The core derivation chain is non-circular. Theorem 1 is proved from Lemma 2 (escape-time estimate, itself from Kac's formula and a coupling) and Lemma 3 (deterministic packing bound using the independently defined parameters f(n) and g(r)); the corollaries are elementary consequences, and no fitted parameter is later renamed as a prediction. Proposition 1's sharpness rests on the standard lollipop hitting-time lower bound attributed to [2,3,4], an external benchmark, not on the theorem being proved; relying on an unproved external bound is a fragility, not a circularity. Proposition 2 is a direct occupation-time identity whose limitations are explicitly acknowledged. The only author-overlap citation, [1] (Benjamini–Gurel-Gurevich–Schramm), is used for background references and carries no load. Under the reviewing instruction to flag missing support: the Abstract announces a proof that vertex nonamenability implies linear range, but the supplied body states only 'Conjecture 1' in Section 4 and gives no Dirichlet-inequality or escape-probability derivation; this is a substantive absent-proof/consistency problem, but it is not a circular reduction, so it does not raise the circularity score.
Assumptions & free parameters
assumptions (6)
- standard math Kac's formula E_y[τ_y⁺] = 2|F|/deg(y) for finite connected graphs
- standard math Strong Markov property and the coupling of the walk on G with the walk on the induced-subgraph-plus-path H in Lemma 2
- standard math Lollipop hitting-time lower bound E[τ_end] ≥ cn³
- standard math Return probability bound P_x(X_t=x) ≤ 4 deg(x)/√t
- domain assumption Classical equivalence of vertex-nonamenability and spectral gap on bounded-degree graphs
- ad hoc to paper Vertex expansion ι_V>0 ⇒ unweighted Dirichlet inequality ⇒ uniform positive escape probability from every vertex
Cite this review
Pith. "Pith review of How fast does the range of simple random walk grow?." pith.science (2026). https://pith.science/paper/J6YJ6SQI
@misc{pith2026260211051,
author = {Pith},
title = {Pith review of: How fast does the range of simple random walk grow?},
year = {2026},
howpublished = {\url{https://pith.science/paper/J6YJ6SQI}},
note = {Machine review of arXiv:2602.11051}
}
abstract
Consider a discrete-time simple random walk $(X_t)_{t\ge 0}$ on an infinite, connected, locally finite simple graph $G$, and let \[ R_t := |\{X_0,\ldots,X_t\}| \] denote its range. The main result of this revised note is that positive vertex isoperimetry already forces linear expected range, with no bounded-degree assumption: if \[ \iota_V(G) := \inf_{0<|S|<\infty} \frac{|\partial_V S|}{|S|} >0, \] then $\E_x R_t \ge c(G)(t+1)$ for every starting vertex $x$ and every $t\ge 0$. The proof is direct: vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex. We also record a finite counterpart: in an $n$-vertex finite vertex expander, the expected hitting time of an independent stationary random target is $\Theta(n)$, again with no restriction on degrees. We also record a chain of geometrically growing lollipops for which \[ \E_o R_t \asymp t^{1/3}, \] so the subdiffusive exponent $1/3$ need not be accompanied by superdiffusive oscillations. In particular, for this graph the lower and upper logarithmic exponents of $\E_oR_t$ are both equal to $1/3$. Finally, since Barnes and Feige proved the sharp universal estimate $\E T_n= O(n^3)$ for the $n$-th discovery time, we move our elementary proof of the weaker bound $\E T_n=O(n^3\log n)$ to a later section as a short self-contained argument with a logarithmic loss. We close with a related bounded-degree mixing statement: if the lazy walk has worst-case mixing time $m$, then at least $c\sqrt m$ starting vertices are still noticeably unmixed at time $\lfloor m/2\rfloor$. This final result uses the same commute-time/effective-resistance control of connected sets that appears throughout the paper.
Figures
Reference graph
Works this paper leans on
-
[1]
Benjamini, O
I. Benjamini, O. Gurl-Gurevich, and O. Schramm, Cutpoints and resistance of random walk paths.Annals of Probability39(3), 1122-1136, 2011
2011
-
[2]
Brightwell, and P
G. Brightwell, and P. Winkler, Maximum hitting time for random walks on graphs. Random Structures & Algorithms, 1(3):263–276, 1990
1990
-
[3]
Feige, A tight upper bound on the cover time for random walks on graphs.Random Structures & Algorithms6(1):51–54, 1995
U. Feige, A tight upper bound on the cover time for random walks on graphs.Random Structures & Algorithms6(1):51–54, 1995
1995
-
[4]
Jonasson, Lollipop graphs are extremal for commute times.Random Structures and Algorithms, 16(2):131–142, 2000
J. Jonasson, Lollipop graphs are extremal for commute times.Random Structures and Algorithms, 16(2):131–142, 2000
2000
-
[5]
Asymptotic enumeration of spanning trees.Combin
Russell Lyons. Asymptotic enumeration of spanning trees.Combin. Probab. Comput. 14(4): 491–522, 2005
2005
-
[6]
Lyons and Y
R. Lyons and Y. Peres.Probability on Trees and Networks. Cambridge University Press, 2016. 8
2016
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.