MIXING TIME ESTIMATION IN REVERSIBLE MARKOV CHAINS FROM A SINGLE SAMPLE PATH

• 成果类型: Article
• 署名作者: Hsu, Daniel; Kontorovich, Aryeh; Levin, David A.; Peres, Yuval; Szepesvari, Csaba; Wolfer, Geoffrey
• 署名单位: Columbia University; Columbia University; Ben-Gurion University of the Negev; University of Oregon; Microsoft; University of Alberta
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/18-AAP1457
• 发表日期: 2019
• 页码: 2439-2480
• 关键词: perturbation bounds; Finite; probabilities; distributions; CONVERGENCE; exploration; extension; chernoff; inverse; THEOREM

摘要

The spectral gap gamma(star) of a finite, ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix P may be unknown, yet one sample of the chain up to a fixed time n may be observed. We consider here the problem of estimating gamma(star) from this data pi Let p be the stationary distribution of P, and pi(star) = min(x) pi(x). We show that if n is at least 1/gamma(star)pi(star) times a logarithmic correction, then gamma(star) can be estimated to within a multiplicative factor with high probability. When pi is uniform on d states, this nearly matches a lower bound of d/gamma(star) steps required for precise estimation of gamma(star) Moreover, we provide the first procedure for computing a fully data-dependent interval, from a single finite-length trajectory of the chain, that traps the mixing time t(mix) of the chain at a prescribed confidence level. The interval does not require the knowledge of any parameters of the chain. This stands in contrast to previous approaches, which either only provide point estimates, or require a reset mechanism, or additional prior knowledge. The interval is constructed around the relaxation time t(relax) = 1/gamma(star), which is strongly related to the mixing time, and the width of the interval converges to zero roughly at a 1/root n rate, where n is the length of the sample path.