# Mixing time estimation in reversible Markov chains from a single sample path

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2017.

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

- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [BR-SNIS: Bias Reduced Self-Normalized Importance Sampling](https://mlsanity.com/paper/2207.06364/) (2022)
- [Quantum-enhanced Markov chain Monte Carlo](https://mlsanity.com/paper/2203.12497/) (2022)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [Kernelized Diffusion maps](https://mlsanity.com/paper/2302.06757/) (2023)
- [Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence](https://mlsanity.com/paper/2404.05819/) (2024)
- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [How good is Good-Turing for Markov samples?](https://mlsanity.com/paper/2102.01938/) (2021)
- [Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View](https://mlsanity.com/paper/2207.12217/) (2022)
- [Conformal Predictions under Markovian Data](https://mlsanity.com/paper/2407.15277/) (2024)
- [Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds](https://mlsanity.com/paper/2410.21702/) (2024)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds](https://mlsanity.com/paper/2111.07372/) (2021)
- [Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes](https://mlsanity.com/paper/2402.07296/) (2024)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Generalization for slowly mixing processes](https://mlsanity.com/paper/2305.00977/) (2023)
- [Quantifying Human Priors over Social and Navigation Networks](https://mlsanity.com/paper/2402.18651/) (2024)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigation](https://mlsanity.com/paper/2306.06192/) (2023)
- [Linear Bandits with Non-i.i.d. Noise](https://mlsanity.com/paper/2505.20017/) (2025)
- [Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds](https://mlsanity.com/paper/2610.20007/) (2026)

## Abstract (arXiv)

The spectral gap γ of a finite, ergodic, and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix P may be unknown, yet one sample of the chain up to a fixed time n may be observed. We consider here the problem of estimating γ from this data. Let π be the stationary distribution of P, and π_star = minx π(x). We show that if n = tildeObigl(frac1γ π_starbigr), then γ can be estimated to within multiplicative constants with high probability. When π is uniform on d states, this matches (up to logarithmic correction) a lower bound of tildeOmegabigl(fracdγbigr) steps required for precise estimation of γ. Moreover, we provide the first procedure for computing a fully data-dependent interval, from a single finite-length trajectory of the chain, that traps the mixing time tmix of the chain at a prescribed confidence level. The interval does not require the knowledge of any parameters of the chain. This stands in contrast to previous approaches, which either only provide point estimates, or require a reset mechanism, or additional prior knowledge. The interval is constructed around the relaxation time trelax = 1/γ, which is strongly related to the mixing time, and the width of the interval converges to zero roughly at a 1/√n rate, where n is the length of the sample path.