Optimal lower bound for the variance of hitting times for simple random walks on graphs
Rafael Chiclana, Yuval Peres · arXiv (Cornell University) · 2023
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$.