Cutoff phenomena for random walks on random regular graphs

DOI10.1215/00127094-2010-029zbMATH Open1202.60012arXiv0812.0060OpenAlexW2033635202WikidataQ105584385 ScholiaQ105584385MaRDI QIDQ984454FDOQ984454

Eyal Lubetzky, Allan Sly

Publication date: 19 July 2010

Published in: Duke Mathematical Journal (Search for Journal in Brave)

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 $dgeq3$ is an expander, and even essentially Ramanujan, implying a mixing-time of $O(logn)$. 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))lo{g}_{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 $dgeq3$, the simple random walk on $G(n,d)$ w.h.p. has cutoff at $fracdd-2lo{g}_{d-1}n$ with window order $sqrtlogn$. Surprisingly, the non-backtracking random walk on $G(n,d)$ w.h.p. has cutoff already at $lo{g}_{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.

Full work available at URL: https://arxiv.org/abs/0812.0060

Recommendations

• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff for random lifts of weighted graphs
• Comparing mixing times on sparse random graphs
• Cutoff on all Ramanujan graphs
• Random walks on the random graph

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Random walks on graphs (05C81)

Cites Work

• The non-backtracking spectrum of the universal cover of a graph
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Title not available (Why is that?)
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Random graph dynamics
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Title not available (Why is that?)
• The cutoff phenomenon in finite Markov chains.
• A proof of Alon’s second eigenvalue conjecture and related problems
• Title not available (Why is that?)
• The cutoff phenomenon for ergodic Markov processes
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Title not available (Why is that?)
• Limiting behavior for the distance of a random walk
• Minimization algorithms and random walk on the d-cube
• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• Title not available (Why is that?)
• Total variation cutoff in birth-and-death chains
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Recursive construction for 3-regular expanders

Cited In (65)

• The spectral gap of sparse random digraphs
• Cutoff phenomenon for random walks on Kneser graphs
• Contact process on a graph with communities
• Cutoff for General Spin Systems with Arbitrary Boundary Conditions
• The degree-wise effect of a second step for a random walk on a graph
• Simple random walk on long range percolation clusters. I: Heat kernel bounds
• Cutpoints of non-homogeneous random walks
• Cut-off phenomenon for Ornstein-Uhlenbeck processes driven by Lévy processes
• Random doubly stochastic tridiagonal matrices
• Random walks and local cuts in graphs
• Cutoff for random lifts of weighted graphs
• Complex networks: structure and functionality
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• Cutoff for permuted Markov chains
• Correction to: ``Speeding up Markov chains with deterministic jumps
• Limiting behavior for the distance of a random walk
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Cutoff at the ``entropic time for sparse Markov chains
• An exposition to information percolation for the Ising model
• Local Kesten-McKay law for random regular graphs
• Spectral gap in random bipartite biregular graphs and applications
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• No cutoff in spherically symmetric trees
• Some spectral properties of the non-backtracking matrix of a graph
• On Active and Passive Testing
• Level-set percolation of the Gaussian free field on regular graphs II: finite expanders
• The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
• Mixing time trichotomy in regenerating dynamic digraphs
• Comparing mixing times on sparse random graphs
• Random walk on sparse random digraphs
• No cutoff for circulants: an elementary proof
• Deterministic walks with choice
• Survival and extinction of epidemics on random graphs with general degree
• Mixing time of PageRank surfers on sparse random digraphs
• Cutoff on Ramanujan complexes and classical groups
• Cutoff on all Ramanujan graphs
• Cutoff for the Ising model on the lattice
• CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS
• The cut metric, random graphs, and branching processes
• Cutoff phenomenon for the simple exclusion process on the complete graph
• Cutpoints and Exchangeable Events for Random Walks
• Mixing times of random walks on dynamic configuration models
• Information percolation and cutoff for the stochastic Ising model
• Spectra of lifted Ramanujan graphs
• Random walks on the random graph
• Speeding up Markov chains with deterministic jumps
• Universality of cutoff for graphs with an added random matching
• Critical value asymptotics for the contact process on random graphs
• Cutoff for a stratified random walk on the hypercube
• Linking the mixing times of random walks on static and dynamic random graphs
• A phase transition for repeated averages
• A threshold for cutoff in two-community random graphs
• Random walks on Ramanujan complexes and digraphs
• Discordant edges for the voter model on regular random graphs
• Scale-free percolation mixing time
• Rankings in directed configuration models with heavy tailed in-degrees
• Cutoff profile of the metropolis biased card shuffling
• The varentropy criterion is sharp on expanders
• Excessive symmetry can preclude cutoff
• Simple versus nonsimple loops on random regular graphs
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Cutoff for non-negatively curved Markov chains
• Cutoff on trees is rare
• Speeding up random walk mixing by starting from a uniform vertex

This page was built for publication: Cutoff phenomena for random walks on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q984454)