A Central Limit Theorem for the average target hitting time for a random walk on a random graph

2021/04/02 by Löwe, Matthias, Terveer, Sara
#05C80 #60F05 #60G50 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2104.01053

Abstract

Consider a simple random walk on a realization of an Erdős-Rényi graph. Assume that it is asymptotically almost surely (a.a.s.) connected. Conditional on an eigenvector delocalization conjecture, we prove a Central Limit Theorem (CLT) for the average target hitting time. By the latter we mean the expected time it takes the random walk on average to first hit a vertex j when starting in a fixed vertex i. The average is taken with respect to π_i, the invariant measure of the random walk.

Related

• A Central Limit Theorem for the mean starting hitting time for a random walk on a random graph
• Concentration of Hitting Times in Erdös-Rényi graphs
• Spectral properties of the stochastic block model and their application to hitting times of random walks
• On hitting times for simple random walk on dense Erdös-Rényi random graphs
• Optimal lower bound for the variance of hitting times for simple random walks on graphs