Cutoff for nonbacktracking random walks on sparse random graphs

DOI10.1214/16-AOP1100zbMATH Open1372.60101arXiv1504.02429OpenAlexW2964318841MaRDI QIDQ2012250FDOQ2012250

Authors: Anna Ben-Hamou, Justin Salez 

Publication date: 28 July 2017

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: A finite ergodic Markov chain is said to exhibit cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Discovered in the context of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now believed to be rather typical among fast mixing Markov chains. Yet, establishing it rigorously often requires a challengingly detailed understanding of the underlying chain. Here we consider non-backtracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window, and prove that the (suitably rescaled) cutoff profile approaches a remarkably simple, universal shape.

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

Recommendations

• Random walk on sparse random digraphs
• Cutoff phenomena for random walks on random regular graphs
• Comparing mixing times on sparse random graphs
• Comparing mixing times on sparse random graphs
• A threshold for cutoff in two-community random graphs

zbMATH Keywords

random graphcutoffnonbacktracking random walk

Mathematics Subject Classification ID

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)

Cited In (36)

• Cutoff phenomenon for random walks on Kneser graphs
• The degree-wise effect of a second step for a random walk on a graph
• An entropic proof of cutoff on Ramanujan graphs
• Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs
• Harmonic measure for biased random walk in a supercritical Galton-Watson tree
• Rankings in directed configuration models with heavy tailed in-degrees
• Cutoff at the entropic time for random walks on covered expander graphs
• Cutoff profile of the metropolis biased card shuffling
• Cutoff for random lifts of weighted graphs
• Complex networks: structure and functionality
• Cutoff for permuted Markov chains
• The varentropy criterion is sharp on expanders
• Comparing mixing times on sparse random graphs
• Cutoff at the ``entropic time for sparse Markov chains
• The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise
• Mixing time trichotomy in regenerating dynamic digraphs
• Comparing mixing times on sparse random graphs
• Random walk on sparse random digraphs
• Mixing time of PageRank surfers on sparse random digraphs
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Reversibility of the non-backtracking random walk
• The cut metric, random graphs, and branching processes
• Cutoff phenomenon for the simple exclusion process on the complete graph
• Limit profiles for reversible Markov chains
• Cutoff phenomena for random walks on random regular graphs
• Mixing times of random walks on dynamic configuration models
• Random walks on the random graph
• Extremal cuts of sparse random graphs
• Correlation bounds for distant parts of factor of IID processes
• Random walks on dynamic configuration models: a trichotomy
• Universality of cutoff for graphs with an added random matching
• Cutoff for non-negatively curved Markov chains
• Linking the mixing times of random walks on static and dynamic random graphs
• Cutoff on trees is rare
• Speeding up random walk mixing by starting from a uniform vertex
• A threshold for cutoff in two-community random graphs

This page was built for publication: Cutoff for nonbacktracking random walks on sparse random graphs

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