A central limit theorem for the mean starting hitting time for a random walk on a random graph (Q6103737)

The authors establish a central limit theorem for hitting times in a random walk on an Erdős-Rényi random graph. Consider the graph \(G(n,p_n)\) with \(n\) vertices and each pair of vertices joined by an edge with probability \(p_n\) such that \(np_n^2/(\log n)^{16\xi}\to\infty\) as \(n\to\infty\), where \(\xi>1\) is a sufficiently large constant independent of \(n\). This choice ensures that the graph is asymptotically almost surely connected. To construct a sequence of such graphs, the authors increment the indicators of the existence of an edge between vertices \(i\) and \(j\) via an appropriate time-inhomogeneous Markov chain for each \(\{i,j\}\) with \(i\not=j\). On a given graph with fixed \(n\), a discrete-time random walk evolves by choosing a neighbour of the current location to which to move, each with equal probability. Let \(H_{i,j}\) denote the expected time such a random walk takes to reach vertex \(j\), when started from vertex \(i\). The main result of the present paper is a central limit theorem for \(H=\sum_j\pi_jH_{i,j}\) for fixed \(i\), where \(\pi_j\) is the stationary probability at vertex \(j\) for the random walk, which is proportional to the degree of vertex \(j\). That is, the authors show that, suitably normalized, \(H\) converges in distribution to Gaussian as \(n\to\infty\). The normalization and parameters of the limiting Gaussian distribution are given explicitly.