A Central Limit Theorem for the mean starting hitting time for a random walk on a random graph

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

paper · doi:10.48550/arxiv.2003.13011

Abstract

We consider simple random walk on a realization of an Erdős-Rényi graph that is asymptotically almost surely (a.a.s.) connected. We show a Central Limit Theorem (CLT) for the average starting hitting time, i.e. the expected time it takes the random walker on average to first hit a vertex j when starting in a fixed vertex i. The average is taken with respect to π_j, the invariant measure of the random walk.

Related

• A Central Limit Theorem for the average target hitting time for a random walk on a random graph
• Concentration of Hitting Times in Erdös-Rényi graphs
• Hitting Time Distributions of Random Walks on Finite Graphs
• On hitting times for simple random walk on dense Erd "os-R 'enyi random\n graphs
• Hitting times in the binomial random graph