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

Let (V,E)(V,E) be a realization of the Erdös–Rényi random graph model G(N,p)G(N,p) and (Xn)n∈N(Xn)n∈N be a simple random walk on it. We study the size of ∑i∈Vπihij∑i∈Vπihij where πi=di/2|E|πi=di/2|E| for didi the number of neighbors of node ii and hijhij the hitting time for (Xn)n∈N(Xn)n∈N between nodes ii and jj. We always consider a regime of p=p(N)p=p(N) such that realizations of G(N,p)G(N,p) are almost surely connected as N→∞N→∞. Our main result is that ∑i∈Vπihij∑i∈Vπihij is almost surely of order N(1+o(1))N(1+o(1)) as N→∞N→∞. This coincides with previous non-rigorous results in the physics literature (Sood et al., 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)G(N,p) (Chung and Lu, 2006) together with bounds on the spectrum of the (random) adjacency matrix of G(N,p)G(N,p) (Erdős et al., 2011).