Estimating the Mixing Time of Ergodic Markov Chains
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:31203159, 2019.
Abstract
We address the problem of estimating the mixing time $t_{\mathsf{mix}}$ of an arbitrary ergodic finite Markov chain from a single trajectory of length $m$. The reversible case was addressed by Hsu et al. [2018+], 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 selfadjoint, and Weyl’s inequality allows for a dimensionfree perturbation analysis of the empirical eigenvalues. As Hsu et al. point out, in the absence of reversibility (and hence, the nonsymmetry of the pair probabilities matrix), the existing perturbation analysis has a worstcase exponential dependence on the number of states $d$. Furthermore, even if an eigenvalue perturbation analysis with better dependence on $d$ were available, in the nonreversible 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 pseudospectral gap instead, which allows us to overcome the loss of selfadjointness and to achieve a polynomial dependence on $d$ and the minimal stationary probability $\pi_\star$. Additionally, in the reversible case, we obtain simultaneous nearly (up to logarithmic factors) minimax rates in $t_{\mathsf{mix}}$ 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 the pseudospectral gap, which shrink to zero at a rate of roughly $1/\sqrt m$, and improve the state of the art in even the reversible case.
Related Material


