Random walks on the random graph

By Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, Allan Sly. 2015

64 citations recorded by the source corpus.

We study random walks on the giant component of the Erd\H{o}s-R\'enyi random graph ${\cal 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 {\bf d})^{-1}\log n \pm (\log n)^{1/2+o(1)}$, where $\nu$ and ${\bf d}$ are the speed of random walk and dimension of harmonic measure on a ${\rm 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 non-backtracking random walk.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f3ffd3f400a082a2b58d5e61581f2466d473dd98

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Random walk on sparse random digraphs (2015, methodology): “The lack of time-reversibility is not a problem at all here, and a similar argument was actually used in [6,8] for undirected graphs.”
Cutoff for non-negatively curved Markov chains (2021, background): “This is inspired by a recent body of works establishing cutoff on random instances [45, 9, 11, 14, 15, 8, 19, 16, 35, 31], where entropy plays a crucial role (see also [50, 55]).”