Random walks on the random graph

2015/04/08 by Nathanaël Berestycki, Berestycki, Nathanael, Eyal Lubetzky +5
Mathematics · #05C80 #60B10 #60G50 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1504.01999

openalex publication_date 2015/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study random walks on the giant component of the Erdős-Rényi random graph \cal G(n,p) where p=λ/n for λ>1 fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order log² n. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to O(log n) and concentrates it (the cutoff phenomenon occurs): the typical mixing is at (ν\bf d)^-1log n ± (log n)^1/2+o(1), where ν and \bf d are the speed of random walk and dimension of harmonic measure on a \rm Poisson(λ)-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.

Related

• Comparing mixing times on sparse random graphs
• Anatomy of a young giant component in the random graph
• Mixing time of the random walk on the giant component of the random geometric graph
• Speeding up random walk mixing by starting from a uniform vertex
• Cutoff for random walks on graphs with bottlenecks