Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
This provides a computationally efficient solution for estimating spectral gaps in large-scale Markov chains, which is incremental but addresses a known bottleneck in existing methods.
The paper tackles the problem of estimating the spectral gap of a Markov chain from sample paths, proposing the UCPI algorithm that achieves time O(n) and memory O((ln n)^2) complexity, enabling application to large state spaces.
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.