Nonconcentration of hitting times for random walks on graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909052724838400 |
|---|---|
| author | Chiclana, Rafael |
| author_facet | Chiclana, Rafael |
| contents | 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(τ_y)+\mathbb E_xτ_y \ge \frac{(\mathbb E_xτ_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τ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17513 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nonconcentration of hitting times for random walks on graphs Chiclana, Rafael Probability 60J10, 05C81 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(τ_y)+\mathbb E_xτ_y \ge \frac{(\mathbb E_xτ_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τ_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. |
| title | Nonconcentration of hitting times for random walks on graphs |
| topic | Probability 60J10, 05C81 |
| url | https://arxiv.org/abs/2605.17513 |