Computationally Efficient Estimation of the Spectral Gap of a Markov Chain

We consider the problem of estimating from sample paths the absolute spectral gap γ_* of a reversible, irreducible and aperiodic Markov chain (Xt)_t ∈ mathbbN over a finite state space 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.