Total-variation cutoff in birth-and-death chains
Preprint
Abstract
The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. In 1996, Diaconis surveyed this phenomenon, and asked how one could recognize its occurrence in families of finite ergodic Markov chains. In 2004, the third author noted that a necessary condition for cutoff in a family of reversible chains is that the product of the mixing-time and spectral-gap tends to infinity, and conjectured that in many settings, this condition should also be sufficient. Diaconis and Saloff-Coste (2006) verified this conjecture for birth-and-death chains with the convergence measured in separation. It is natural to ask whether the conjecture holds for these chains in the more widely used total-variation distance. In this work, we confirm the above conjecture for all continuous-time or lazy discrete-time birth-and-death chains, with convergence measured via total-variation distance. Namely, if the product of the mixing-time and spectral-gap tends to infinity, the chains exhibit cutoff at the maximal hitting time of the stationary distribution median, with a window of at most the geometric mean between the relaxation-time and mixing-time.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- On Times to Quasi-stationarity for Birth and Death ProcessesJournal of Theoretical Probability, 2009
- The Passage Time Distribution for a Birth-and-Death Chain: Strong Stationary Duality Gives a First Stochastic ProofJournal of Theoretical Probability, 2009
- The Mixing Time Evolution of Glauber Dynamics for the Mean-Field Ising ModelCommunications in Mathematical Physics, 2009
- Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastabilityProbability Theory and Related Fields, 2008
- Separation cut-offs for birth and death chainsThe Annals of Applied Probability, 2006
- The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences, 1996
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981
- Coincidence properties of birth and death processesPacific Journal of Mathematics, 1959