Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
Richard S. Combes, Mikaël Touati · 2019
We consider the problem of estimating from sample paths the absolute spectral gap 1-λ⋆ of a reversible, irreducible and aperiodic Markov chain (Xt)t∈N over a finite state space Ω. We propose the UCPI (Upper Confidence Power Iteration) algorithm for this problem, a low-complexity algorithm which estimates the spectral gap in time O(n) and memory space O((ln n)2 given n samples. This is in stark contrast with most known methods which require at least memory space O(|Ω|), so that they cannot be applied to large state spaces. Furthermore, UCPI is amenable to parallel implementation.