CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS

• 成果类型: Article
• 署名作者: Basu, Riddhipratim; Hermon, Jonathan; Peres, Yuval
• 署名单位: Stanford University; University of California System; University of California Berkeley; Microsoft
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/16-AOP1090
• 发表日期: 2017
• 页码: 1448-1487
• 关键词: death chains; times; birth

摘要

A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of worst (in some sense) sets of stationary measure at least a, for some alpha is an element of(0,1). We also give general bounds on the total variation distance of a reversible chain at time tin terms of the probability that some worst set of stationary measure at least alpha was not hit by time t. As an application of our techniques, we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the product of their spectral gaps and their (lazy) mixing-times tends to infinity.