Random walks on the random graph
Authors:
- Nathanaël BerestyckiNBNathanaël Berestycki
- Eyal LubetzkyELEyal Lubetzky
- Yuval PeresYPYuval Peres
- Allan SlyASAllan Sly
- 1 January 2018
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 46 (1) , 456-490
Abstract
We study random walks on the giant component of the Erdős–Rényi random graph $\mathcal{G}(n,p)$ where $p=\lambda/n$ for $\lambda>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^{2}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 $(\nu\mathbf{d})^{-1}\log n\pm(\log n)^{1/2+o(1)}$, where $\nu$ and $\mathbf{d}$ are the speed of random walk and dimension of harmonic measure on a $\operatorname{Poisson}(\lambda)$-Galton–Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the nonbacktracking random walk.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Mixing time of near-critical random graphsThe Annals of Probability, 2012
- Anatomy of a young giant component in the random graphRandom Structures & Algorithms, 2010
- Cutoff phenomena for random walks on random regular graphsDuke Mathematical Journal, 2010
- Critical random graphs: Diameter and mixing timeThe Annals of Probability, 2008
- The evolution of the mixing rate of a simple random walk on the giant component of a random graphRandom Structures & Algorithms, 2008
- Large deviations for random walks on Galton–Watson trees: averaging and uncertaintyProbability Theory and Related Fields, 2002
- Biased random walks on Galton–Watson treesProbability Theory and Related Fields, 1996
- Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measureErgodic Theory and Dynamical Systems, 1995
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984