Random walks on the random graph

Authors:
  • NBNathanaël Berestycki
    Nathanaël Berestycki
  • ELEyal Lubetzky
    Eyal Lubetzky
  • YPYuval Peres
    Yuval Peres
  • ASAllan Sly
    Allan Sly

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.

This publication has 26 references indexed in Scilit: