Cutoff phenomena for random walks on random regular graphs

Abstract

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\ge 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\ge 3$, 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.

33 pages, 4 figures

References in corpus (2)

• Non-backtracking random walks mix faster
• The Non-Backtracking Spectrum of the Universal Cover of a Graph

Cited by in corpus (28)

• Local Kesten--McKay law for random regular graphs
• Cutoff for the Ising model on the lattice
• Giant vacant component left by a random walk in a random d-regular graph
• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Rapid Mixing of Hypergraph Independent Set
• Spectral gap in random bipartite biregular graphs and applications
• On active and passive testing
• Survival and extinction of epidemics on random graphs with general degrees
• Cutoff at the entropic time for random walks on covered expander graphs
• Linking the mixing times of random walks on static and dynamic random graphs
• Cutoff for Almost All Random Walks on Abelian Groups
• Cutoff for Ramanujan graphs via degree inflation
• Total Variation and Separation Cutoffs are not equivalent and neither one implies the other
• A phase transition for repeated averages
• The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill
• Cutoff profile of the Metropolis biased card shuffling
• Cutoff on Ramanujan complexes and classical groups
• Discordant edges for the voter model on regular random graphs
• Gradual convergence for Langevin dynamics on a degenerate potential
• Cut-off phenomenon for Ornstein-Uhlenbeck processes driven by Lévy processes
• Spectral properties of the non-backtracking matrix of a graph
• Cutoff for Contingency Table and Torus Random Walks with Low Incremental Correlations
• Mixing trichotomy for random walks on directed stochastic block models
• Profile cut-off phenomenon for the ergodic Feller root process
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Dull cut off for circulants
• Excessive symmetry can preclude cutoff
• Mixing of fast random walks on dynamic random permutations