PreprintCC BY 4.0arXiv
On the Impossibility of Estimating the Average Mixing Time
Abstract
We establish nearly-matching converse bounds on the sample complexity of estimating the average mixing time of a Markov chain from a single stationary trajectory. Unlike the worst-case mixing time, which maximises the total-variation distance to stationarity over all initial states, the average mixing time averages this distance under the stationary distribution and can therefore be substantially smaller. Our converse bounds establish when estimation is impossible, and match the key dependencies in existing achievability bounds, up to logarithmic factors. Together, these bounds provide nearly-tight PAC guarantees for estimating the average mixing time.
Related
- A mixing time method for estimating the sample complexity of quantum state discrimination
- Estimating Average Treatment Effects with Projected Instrumental Variables
- Imputation is all you need: double robustness, semiparametric efficiency, and automatic covariate balance for estimating the average treatment effect
- Estimating the average treatment effect under limited overlap via Polynomial Approximation and Extrapolation
- Estimating Group Average Treatment Effects in High-Risk Populations with Unobserved Target Membership
BibTeX
@misc{judd2026impossibility,
title = {{On the Impossibility of Estimating the Average Mixing Time}},
author = {Nathan A. Judd and Amedeo Roberto Esposito},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10860},
eprint = {2610.10860},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10860},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Impossibility of Estimating the Average Mixing Time
AU - Nathan A. Judd
AU - Amedeo Roberto Esposito
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10860
UR - https://arxiv.org/abs/2610.10860
AB - We establish nearly-matching converse bounds on the sample complexity of estimating the average mixing time of a Markov chain from a single stationary trajectory. Unlike the worst-case mixing time, which maximises the total-variation distance to stationarity over all initial states, the average mixing time averages this distance under the stationary distribution and can therefore be substantially smaller. Our converse bounds establish when estimation is impossible, and match the key dependencies in existing achievability bounds, up to logarithmic factors. Together, these bounds provide nearly-tight PAC guarantees for estimating the average mixing time.
ER -