Mixing Time Estimation in Ergodic Markov Chains from a Single Trajectory with Contraction Methods
share
The mixing time t_mix of an ergodic Markov chain measures the rate of convergence towards its stationary distribution π. We consider the problem of estimating t_mix from one single trajectory of m observations (X_1, . . . , X_m), in the case where the transition kernel M is unknown, a research program started by Hsu et al. [2015]. The community has so far focused primarily on leveraging spectral methods to estimate the relaxation time t_rel of a reversible Markov chain as a proxy for t_mix. Although these techniques have recently been extended to tackle non-reversible chains, this general setting remains much less understood. Our new approach based on contraction methods is the first that aims at directly estimating t_mix up to multiplicative small universal constants instead of t_rel. It does so by introducing a generalized version of Dobrushin's contraction coefficient κ_gen, which is shown to control the mixing time regardless of reversibility. We subsequently design fully data-dependent high confidence intervals around κ_gen that generally yield better convergence guarantees and are more practical than state-of-the-art.
READ FULL TEXT