Empirical and Instance-Dependent Estimation of Markov Chain and Mixing Time
This work provides more accurate and computationally efficient methods for estimating mixing times in Markov chains, which is important for applications in statistics and machine learning, though it is incremental in building on prior contraction-based techniques.
The paper tackles the problem of estimating the mixing time of a Markov chain from a single trajectory, using a contraction-based approach instead of spectral methods, resulting in improved data-dependent confidence intervals and instance-dependent rates for estimation.
We address the problem of estimating the mixing time of a Markov chain from a single trajectory of observations. Unlike most previous works which employed Hilbert space methods to estimate spectral gaps, we opt for an approach based on contraction with respect to total variation. Specifically, we estimate the contraction coefficient introduced in Wolfer [2020], inspired from Dobrushin's. This quantity, unlike the spectral gap, controls the mixing time up to strong universal constants and remains applicable to non-reversible chains. We improve existing fully data-dependent confidence intervals around this contraction coefficient, which are both easier to compute and thinner than spectral counterparts. Furthermore, we introduce a novel analysis beyond the worst-case scenario by leveraging additional information about the transition matrix. This allows us to derive instance-dependent rates for estimating the matrix with respect to the induced uniform norm, and some of its mixing properties.