IMPROVED ESTIMATION OF RELAXATION TIME IN NONREVERSIBLE MARKOV CHAINS

• 成果类型: Article
• 署名作者: Wolfer, Geoffrey; Kontorovich, Aryeh
• 署名单位: RIKEN; Ben-Gurion University of the Negev
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP1963
• 发表日期: 2024
• 页码: 249-276
• 关键词: algorithms; CONVERGENCE; lanczos; rates

摘要

We show that the minimax sample complexity for estimating the pseudo spectral gap gamma(ps) of an ergodic Markov chain in constant multiplicative error is of the order of (Theta) over tilde (1/gamma(ps)pi(star)), where pi(star) is the minimum stationary probability, recovering the known bound in the reversible setting for estimating the absolute spectral gap (Hsu et al., Ann. Appl. Probab. 29 (2019) 2439-2480), and resolving an open problem of Wolfer and Kontorovich (In Proceedings of the Thirty-Second Conference on Learning Theory (2019) 3120-3159 PMLR). Furthermore, we strengthen the known empirical procedure by making it fully-adaptive to the data, thinning the confidence intervals and reducing the computational complexity. Along the way, we derive new properties of the pseudo-spectral gap and introduce the notion of a reversible dilation of a stochastic matrix.