Nonconcentration of hitting times for random walks on graphs

We study nonconcentration of hitting times for simple random walk on finite graphs. We prove that, for every connected graph with $n$ vertices, $${\mathrm{Var}}_x({\tau }_y)+{\mathbb{E}}_x{\tau }_y\ge \frac{({\mathbb{E}}_x{\tau }_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{\tau }_y$ and the graph distance $\text{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.