Estimating the mixing time of non-reversible Markov chains

The mixing time is a fundamental quantity measuring the rate of convergence of a Markov chain towards its stationary distribution. We will discuss the problem of estimating the mixing time from one single long trajectory of observations. The reversible setting was addressed using spectral methods by Hsu et al. (2015), who left the general case as an open problem. In the reversible setting, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl’s inequality allows for dimension-free perturbation analysis of the empirical eigenvalues. In the absence of reversibility, the existing perturbation analysis has a worst-case exponential dependence on the number of states. Furthermore, even if an eigenvalue perturbation analysis with better dependence on the number of states 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. We design a procedure, using spectral methods, that allows us to overcome the loss of self-adjointness and to recover a sample size with a polynomial dependence in some natural complexity parameters of the chain. Additionally, we will present an alternative estimation procedure that moves away from spectral methods entirely and is instead based on a generalized version of Dobrushin’s contraction. Joint work with Aryeh Kontorovich.

Estimating the Mixing Time of Ergodic Markov Chains Geoffrey Wolfer, Aryeh Kontorovich - COLT2019 http://proceedings.mlr.press/v99/wolfer19a.html
https://arxiv.org/abs/1902.01224

Mixing Time Estimation in Ergodic Markov Chains from a Single Trajectory with Contraction Methods Geoffrey Wolfer - ALT2020 https://arxiv.org/abs/1912.06845