Improved Estimation of Relaxation Time in Non-reversible Markov Chains

2022/09/01 by Wolfer, Geoffrey, Kontorovich, Aryeh · 1 citation
#FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2209.00175

Abstract

We show that the minimax sample complexity for estimating the pseudo-spectral gap γ_ps of an ergodic Markov chain in constant multiplicative error is of the order of Θ( \frac1γ_ps π_⋆ ), where π_⋆ is the minimum stationary probability, recovering the known bound in the reversible setting for estimating the absolute spectral gap [Hsu et al., 2019], and resolving an open problem of Wolfer and Kontorovich [2019]. 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.

Cited by

• Near-Optimal Clustering in Mixture of Markov Chains

Related

• Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory
• Spectral gap of nonreversible Markov chains
• Mixing time estimation in reversible Markov chains from a single sample\n path
• Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
• Estimating the Mixing Time of Ergodic Markov Chains