Total variation cutoff in birth-and-death chains

• 成果类型: Article
• 署名作者: Ding, Jian; Lubetzky, Eyal; Peres, Yuval
• 署名单位: Microsoft; University of California System; University of California Berkeley
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-008-0185-3
• 发表日期: 2010
• 页码: 61-85

摘要

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 pi, the separation 1-p(t) (x, y)/pi(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.