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)

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

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)