# Computationally Efficient Estimation of the Spectral Gap of a Markov Chain

arXiv: https://arxiv.org/abs/1806.06047 · HTML: https://mlsanity.com/paper/1806.06047/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2018.

## Built on by (most cited first, 4 of 4)

- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Conformal Predictions under Markovian Data](https://mlsanity.com/paper/2407.15277/) (2024)
- [Generalization Bounds on Multi-Kernel Learning with Mixed Datasets](https://mlsanity.com/paper/2205.07313/) (2022)
- [Variable-Complexity Weighted-Tempered Gibbs Samplers for Bayesian Variable Selection](https://mlsanity.com/paper/2304.02899/) (2023)

## Abstract (arXiv)

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.