Computationally Efficient Estimation of the Spectral Gap of a Markov Chain

We consider the problem of estimating from sample paths the absolute spectral gap $\gamma_*$ of a reversible, irreducible and aperiodic Markov chain $(X_t)_{t \in \mathbb{N}}$ over a finite state $\Omega$. We propose the ${\tt UCPI}$ (Upper Confidence Power Iteration) algorithm for this problem, a low-complexity algorithm which estimates the spectral gap in time ${\cal O}(n)$ and memory space ${\cal O}((\ln n)^2)$ given $n$ samples. This is in stark contrast with most known methods which require at least memory space ${\cal O}(|\Omega|)$, so that they cannot be applied to large state spaces. Furthermore, ${\tt UCPI}$ is amenable to parallel implementation.