Empirical and Instance-Dependent Estimation of Markov Chain and Mixing
  Time
  We tackle the fundamental 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 valid for non-reversible
chains. We design fully data-dependent confidence intervals around the
coefficient, which are both easier to compute and thinner than their spectral
counterparts. Furthermore, we initiate the beyond worst-case analysis, by
showing how to leverage additional information about the transition matrix in
order to obtain instance-dependent rates for its estimation with respect to the
induced uniform norm, as well as some of its mixing properties.
