Concentration of Hitting Times in Erdös-Rényi graphs

Abstract

We consider Erdős-Rényi graphs $G(n,p)$ for $0<p<1$ fixed and $n\to \infty$ and study the expected number of steps, $H_{wv}$, that a random walk started in $w$ needs to first arrive in $v$. A natural guess is that an Erdős-Rényi random graph is so homogeneous that it does not really distinguish between vertices and $H_{wv}=(1+o(1))n$. Löwe-Terveer established a CLT for the Mean Starting Hitting Time suggesting $H_{wv}=n\pm \mathcal{O}(\sqrt{n})$. We prove the existence of a strong concentration phenomenon: $H_{wv}$ is given, up to a very small error of size $\lesssim \sqrt{\log n}/\sqrt{n}$, by an explicit simple formula involving only the total number of edges $|E|$, the degree of $v$ and the distance $d(v,w)$.

arXiv comment2 figures