2015/04/09 by Anna Ben-Hamou, Justin Salez, Ben-Hamou, Anna +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1504.02429
openalex publication_date 2015/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A finite ergodic Markov chain is said to exhibit cutoff if its distance to\nstationarity remains close to 1 over a certain number of iterations and then\nabruptly drops to near 0 on a much shorter time scale. Discovered in the\ncontext of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now\nbelieved to be rather typical among fast mixing Markov chains. Yet,\nestablishing it rigorously often requires a challengingly detailed\nunderstanding of the underlying chain. Here we consider non-backtracking random\nwalks on random graphs with a given degree sequence. Under a general sparsity\ncondition, we establish the cutoff phenomenon, determine its precise window,\nand prove that the (suitably rescaled) cutoff profile approaches a remarkably\nsimple, universal shape.\n