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 $γ_*$ of a reversible, irreducible and aperiodic Markov chain $(X_t)_{t \in \mathbb{N}}$ over a finite state space $Ω$. 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}(|Ω|)$, so that they cannot be applied to large state spaces. Furthermore, ${\tt UCPI}$ is amenable to parallel implementation.

32 pages