Optimal lower bound for the variance of hitting times for simple random walks on graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910277588484096 |
|---|---|
| author | Chiclana, Rafael Peres, Yuval |
| author_facet | Chiclana, Rafael Peres, Yuval |
| contents | We study hitting times in simple random walks on graphs, which measure the time required to reach specific target vertices. Our main result establishes a sharp lower bound for the variance of hitting times. For a simple random walk on a graph with $n$ vertices, we prove that the variance of the hitting time from a vertex $x$ to a vertex $y$, denoted $τ_y$, is at least of the order $\mathbb{E}_x(τ_y)^2 / \log n$. When the graph is a tree, we show that $n$ can be replaced by the graph's distance between vertices $x$ and $y$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07726 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal lower bound for the variance of hitting times for simple random walks on graphs Chiclana, Rafael Peres, Yuval Probability 05C81, 05C05 We study hitting times in simple random walks on graphs, which measure the time required to reach specific target vertices. Our main result establishes a sharp lower bound for the variance of hitting times. For a simple random walk on a graph with $n$ vertices, we prove that the variance of the hitting time from a vertex $x$ to a vertex $y$, denoted $τ_y$, is at least of the order $\mathbb{E}_x(τ_y)^2 / \log n$. When the graph is a tree, we show that $n$ can be replaced by the graph's distance between vertices $x$ and $y$. |
| title | Optimal lower bound for the variance of hitting times for simple random walks on graphs |
| topic | Probability 05C81, 05C05 |
| url | https://arxiv.org/abs/2312.07726 |