Optimal lower bound for the variance of hitting times for simple random walks on graphs

Abstract

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 ${\tau }_y$, is at least of the order ${\mathbb{E}}_x({\tau }_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$.

There was a mistake in the proof for general graphs. The main result is implied by a result in a recent independent project on the same topic, and thus this note became obsolete. We never sent it to a journal