Optimal lower bound for the variance of hitting times for simple random walks on graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |