On hitting times for simple random walk on dense Erdös-Rényi random graphs

Abstract

Let $G(N,p)=(V,E)$ be an Erdös-Rényi random graph and $(X_n{)}_{n\in \mathbb{N}}$ be a simple random walk on it. We study the the order of magnitude of ${\sum }_{i\in V}{\pi }_i{h}_{ij}$ where ${\pi }_i=d_i/2|E|$ for $d_i$ the number of neighbors of node $i$ and $h_{ij}$ the hitting time for $(X_n{)}_{n\in \mathbb{N}}$ between nodes $i$ and $j$, in a regime of $p=p(N)$ such that $G(N,p)$ is almost surely connected as $N\to \infty$. Our main result is that ${\sum }_{i\in V}{\pi }_i{h}_{ij}$ is almost surely of order $N(1+o(1))$ as $N\to \infty$, which coincides with previous results in the physics literature \cite{sood}, though our techniques are based on large deviations bounds on the number of neighbors of a typical node and the number of edges in $G(N,p)$ together with recent work on bounds on the spectrum of the (random) adjacency matrix of $G(N,p)$.

9 pages