Computationally Efficient Estimation of the Spectral Gap of a Markov Chain

Richard Combes, Mikael Touati

We consider the problem of estimating from sample paths the absolute spectral gap ${\gamma }_{\ast }$ of a reversible, irreducible and aperiodic Markov chain $(X_t{)}_{t\in \mathbb{N}}$ over a fi…