How fast does the range of simple random walk grow?
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910280692269056 |
|---|---|
| author | Benjamini, Itai Salez, Justin |
| author_facet | Benjamini, Itai Salez, Justin |
| contents | 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 \[ ι_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 $Θ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11051 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How fast does the range of simple random walk grow? Benjamini, Itai Salez, Justin Probability 60J10 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 \[ ι_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 $Θ(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. |
| title | How fast does the range of simple random walk grow? |
| topic | Probability 60J10 |
| url | https://arxiv.org/abs/2602.11051 |