Empirical and instance‐dependent estimation of Markov chain and mixing time
研究如何从单条观测轨迹估计马尔可夫链的混合时间，采用基于全变差收缩的方法，改进现有置信区间并引入实例依赖的估计速率。
Abstract 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 nonreversible 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.