Proceedings of the National Academy of Sciences · 1996 · 310 citations · 2 references
EngineeringMathematicsDiscrete MathematicsProbability TheoryStochastic ProcessesMarkov ChainsMarkov ProcessesRandom WalksSymmetry BreakingEigenvaluesFinite Markov ChainsFinite-state Markov ChainsLong-run BehaviorLong-time Behavior
Natural mixing processes modeled by Markov chains often exhibit a sharp cutoff in their convergence to long‑time behavior. This paper presents problems where the cutoff can be proved, such as card shuffling and the Ehrenfests' urn. The authors explore cutoffs in these models, emphasizing the role of high multiplicity of second eigenvalues due to symmetry. They find that chains with polynomial growth, like the drunkard's walk, do not show cutoffs, yet cutoffs can persist even when symmetry is broken.
Natural mixing processes modeled by Markov chains often show a sharp cutoff in their convergence to long-time behavior. This paper presents problems where the cutoff can be proved (card shuffling, the Ehrenfests' urn). It shows that chains with polynomial growth (drunkard's walk) do not show cutoffs. The best general understanding of such cutoffs (high multiplicity of second eigenvalues due to symmetry) is explored. Examples are given where the symmetry is broken but the cutoff phenomenon persists.
2
An Introduction to Probability Theory.
Bert Fristedt, P. A. P. Moran · Journal of the American Statistical Association · 1986 · 3.4K citations