Cutoff phenomena for random walks on random regular graphs

DOI10.1215/00127094-2010-029MaRDI QIDQ984454zbMATH OpenOpenAlexWikidataFDO

Authors Eyal Lubetzky, Allan Sly

Publication date 19 July 2010

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

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

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)

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.

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

Cites work

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

Cited in

(72)

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

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)