Metraipolis › archive › dc_e455b82335df
On the Impossibility of Estimating the Average Mixing Time — arXiv:2610.10860
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10860
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:28:17.062Z
- SHA-256 of the archived text
afee756b015b3200cb09987cc460a6ce0c3ddfcc9aecf8654cb01b9037771ba9- Stable URL of this page
https://metraipolis.com/documento/dc_e455b82335df
How to cite
On the Impossibility of Estimating the Average Mixing Time — arXiv:2610.10860 — arXiv (en), https://arxiv.org/abs/2610.10860 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e455b82335df (Metraipolis archive dc_e455b82335df, sha256 afee756b015b3200cb09987cc460a6ce0c3ddfcc9aecf8654cb01b9037771ba9)
BibTeX
@misc{dce455b82335df,
title = {On the Impossibility of Estimating the Average Mixing Time — arXiv:2610.10860},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10860},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e455b82335df; sha256 afee756b015b3200cb09987cc460a6ce0c3ddfcc9aecf8654cb01b9037771ba9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10860. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno). Categorie arXiv: Statistics Theory (math.ST) ; Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2610.10860 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:52:46.494Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).