The Annals of Probability · 2017 · 45 citations · 23 references
Natural SciencesMathematicsCombinatoricsProbability TheoryStochastic ProcessesErgodic TheoryGraph TheoryMarkov ChainsMarkov ProcessesRandom WalksMarkov Chains On GraphsRandom Graph TheoryRandom GraphsRandom Walk On Markov ChainsRandom Walks On GraphsSparse Random Graphs
A finite ergodic Markov chain exhibits 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 nonbacktracking 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 cutoff profile approaches a remarkably simple, universal shape.
23
On Tail Probabilities for Martingales
David A. Freedman · The Annals of Probability · 1975 · 646 citations · Full text
Shuffling Cards and Stopping Times
David Aldous, Persi Diaconis · American Mathematical Monthly · 1986 · 347 citations