Let $G(N,p)=(V,E)$ be an Erd\"os-R\'enyi 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_ih_{ 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_ih_{ 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)$.
Categories: math.PR