Title: Computationally Efficient Estimation of the Spectral Gap of a Markov Chain,
Abstract: 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.