# Estimating the Mixing Time of Ergodic Markov Chains

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

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

- [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)
- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [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)
- [Hardness in Markov Decision Processes: Theory and Practice](https://mlsanity.com/paper/2210.13075/) (2022)
- [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)
- [On the α-lazy version of Markov chains in estimation and testing problems](https://mlsanity.com/paper/2105.09536/) (2021)
- [Generalization Bounds on Multi-Kernel Learning with Mixed Datasets](https://mlsanity.com/paper/2205.07313/) (2022)
- [Generalization for slowly mixing processes](https://mlsanity.com/paper/2305.00977/) (2023)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Central Limit Theorems for Transition Probabilities of Controlled Markov Chains](https://mlsanity.com/paper/2508.01517/) (2025)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Variable-Complexity Weighted-Tempered Gibbs Samplers for Bayesian Variable Selection](https://mlsanity.com/paper/2304.02899/) (2023)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)
- [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)

We address the problem of estimating the mixing time t_mathsfmix of an arbitrary ergodic finite-state Markov chain from a single trajectory of length m. The reversible case was addressed by Hsu et al. [2019], who left the general case as an open problem. In the reversible case, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl's inequality allows for a dimension-free perturbation analysis of the empirical eigenvalues. As Hsu et al. point out, in the absence of reversibility (which induces asymmetric pair probabilities matrices), the existing perturbation analysis has a worst-case exponential dependence on the number of states d. Furthermore, even if an eigenvalue perturbation analysis with better dependence on d were available, in the non-reversible case the connection between the spectral gap and the mixing time is not nearly as straightforward as in the reversible case. Our key insight is to estimate the pseudo-spectral gap γ_mathsfps instead, which allows us to overcome the loss of symmetry and to achieve a polynomial dependence on the minimal stationary probability π_star and γ_mathsfps. Additionally, in the reversible case, we obtain simultaneous nearly (up to logarithmic factors) minimax rates in t_mathsfmix and precision varepsilon, closing a gap in Hsu et al., who treated varepsilon as constant in the lower bounds. Finally, we construct fully empirical confidence intervals for γ_mathsfps, which shrink to zero at a rate of roughly 1/√m, and improve the state of the art in even the reversible case.