Estimating the Mixing Time of Ergodic Markov Chains
  We address the problem of estimating the mixing time $t_{\mathsf{mix}}$ 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 $\gamma_{\mathsf{ps}}$ instead, which allows us to overcome
the loss of symmetry and to achieve a polynomial dependence on the minimal
stationary probability $\pi_\star$ and $\gamma_{\mathsf{ps}}$. 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
$\gamma_{\mathsf{ps}}$, which shrink to zero at a rate of roughly $1/\sqrt{m}$,
and improve the state of the art in even the reversible case.
