2023/04/09 by Andrea Ottolini, Stefan Steinerberger, Ottolini, Andrea +1
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2304.04289
We consider Erdős-Rényi graphs G(n,p) for 0 < p < 1 fixed and n → ∞ and study the expected number of steps, Hwv, that a random walk started in w needs to first arrive in v. A natural guess is that an Erdős-Rényi random graph is so homogeneous that it does not really distinguish between vertices and Hwv = (1+o(1)) n. Löwe-Terveer established a CLT for the Mean Starting Hitting Time suggesting Hw v = n ± O(√(n)). We prove the existence of a strong concentration phenomenon: Hw v is given, up to a very small error of size \lesssim √logn/√(n), by an explicit simple formula involving only the total number of edges |E|, the degree of v and the distance d(v,w).