Total variation cutoff in birth-and-death chains

Jian Ding, Eyal Lubetzky, Yuval Peres

Research output: Contribution to journalArticle

Abstract

The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. Diaconis [Proc Natl Acad Sci USA 93(4):1659-1664, 1996] surveyed this phenomenon, and asked how one could recognize its occurrence in families of finite ergodic Markov chains. Peres [American Institute of Mathematics (AIM) Research Workshop, Palo Alto. http://www.aimath.org/WWN/mixingtimes, 2004] 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 [Ann Appl Probab 16(4):2098-2122, 2006] verified this conjecture for continuous-time birth-and-death chains, started at an endpoint, with 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. In addition, we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution π, the separation 1 - pt(x, y)/π(y) is maximized when x, y are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains.

Original languageEnglish (US)
Pages (from-to)61-85
Number of pages25
JournalProbability Theory and Related Fields
Volume146
Issue number1
DOIs
StatePublished - Oct 2009

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Total variation cutoff in birth-and-death chains'. Together they form a unique fingerprint.

  • Cite this