Empirical and Instance-Dependent Estimation of Markov Chain and Mixing Time. (arXiv:1912.06845v3 [math.PR] UPDATED)

We tackle the problem of estimating the mixing time of a Markov chain from a
single trajectory of observations. In contrast with previous works which
considered Hilbert space methods to estimate spectral gaps, we opt for an
approach based on contraction with respect to total variation. Specifically, we
define and estimate a generalized contraction coefficient based on Dobrushin's.
We show that this quantity -- unlike the spectral gap -- controls the mixing
time up to strong universal constants and remains …

arxiv markov math pr time