The relaxation time does not control the normal approximation of stationary additive functionals
Let $X$ be a finite irreducible reversible Markov chain in continuous time with relaxation time $\tau_2$, started from its stationary distribution, and let $g$ be a function on its states with mean $0$ and variance $1$ under that distribution. Aldous and Fill asked whether the Kolmogorov distance between $\int_0^tg(X_u)\,du/(\sigma t^{1/2})$, where $\sigma^2$ is the asymptotic variance rate, and the standard normal law is bounded by a function of $\max|g|$ and $t/\tau_2$ alone that tends to $0$ as $t/\tau_2\to\infty$. It is not. For every $b\ge1$ and $s\ge2b$ there are a chain on four states with $\tau_2=1$ and a function $g$ of mean $0$ and variance $1$ with $\max|g|=b$ such that $\int_0^sg(X_u)\,du\le0$ with probability at least $1-4/s$, so at $t=s$ the distance is at least $1/2-4/s$ whatever positive constant the integral is divided by.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-08
- DOI
- https://doi.org/10.5281/zenodo.24069930
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint