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

Löwe M., Torres F.

Abstract

Let (V,E) be a realization of the Erdös-Rényi random graph model G (N, p) and (Xn)n∈N be a simple random walk on it. We study the size of ∑i ∈Vπih i j where πi=di/2|E| for d i the number of neighbors of node i and h i j the hitting time for (Xn)n∈N between nodes i and j. We always consider a regime of p = p (N) such that realizations of G (N, p) are almost surely connected as N → ∞. Our main result is that ∑i ∈Vπih i j is almost surely of order N (1 + o (1) ) as N → ∞. This coincides with previous non-rigorous results in the physics literature (Sood etal., 2004). Our techniques are based on large deviation bounds on the number of neighbors of a typical node and the number of edges in G (N, p) (Chung and Lu, 2006) together with bounds on the spectrum of the (random) adjacency matrix of G (N, p) (Erdos etal., 2011). © 2014 Elsevier B.V.