Cutoff phenomena for random walks on random regular graphs

By Eyal Lubetzky, Allan Sly. 2008

132 citations recorded by the source corpus.

The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are believed to exhibit cutoff, and yet establishing this fact is often extremely challenging. An important such family of chains is the random walk on $\G(n,d)$, a random $d$-regular graph on $n$ vertices. It is well known that almost every such graph for $d\geq 3$ is an expander, and even essentially Ramanujan, implying a mixing-time of $O(\log n)$. According to a conjecture of Peres, the simple random walk on $\G(n,d)$ for such $d$ should then exhibit cutoff with high probability. As a special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random 3-regular graph is w.h.p. $(6+o(1))\log_2 n$. In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple and for non-backtracking random walks on $\G(n,d)$. Namely, for any fixed $d\geq3$, the simple random walk on $\G(n,d)$ w.h.p. has cutoff at $\frac{d}{d-2}\log_{d-1} n$ with window order $\sqrt{\log n}$. Surprisingly, the non-backtracking random walk on $\G(n,d)$ w.h.p. has cutoff already at $\log_{d-1} n$ with constant window order. We further extend these results to $\G(n,d)$ for any $d=n^{o(1)}$ that grows with $n$ (beyond which the mixing time is O(1)), where we establish concentration of the mixing time on one of two consecutive integers.

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

View Paper: https://www.semanticscholar.org/paper/084704f62274c756ab081b45f72593f95ca80162

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

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]).”
Markov Chains and Mixing Times: Second Edition (2017, background): “Updates: This question has been answered for tori by Lubetzky and Sly (2013, 2014a, 2016, 2014b). For general graphs of bounded degree, cutoff at high temperature was established in Lubetzky and Sly (2014b).”
Cutoff on all Ramanujan graphs (2015, methodology): “By the result of Friedman [17] that a random (uniformly chosen) d-regular graph on n vertices is typically weakly Ramanujan (as conjectured by Alon), Theorem 4 then implies cutoff, re-deriving the above mentioned result of [22].”
Random walk on sparse random digraphs (2015, methodology): “This takes after the good idea of ‘roots’ that was introduced by Lubetzky and Sly [33] in the case of regular graphs, and then reused in [6,8] for graphs with more general degrees.”