The variation threshold, Kemeny's constant and stationary times of reversible Markov chains
For finite reversible Markov chains, Aldous and Fill asked whether the variation threshold $\tau_1$ is at most the average hitting time $\tau_0$ (Kemeny's constant), and whether the relaxation time $\tau_2$ is at most $\tau_1^{(2)}$, the largest over initial states of the least mean of a stopping time at which the chain has its stationary distribution. The answer to the first question is no: a birth and death chain on three states with a strong drift has $\tau_1>\tau_0$, and on the analogous chains with $k+1$ states the ratio $\tau_1/\tau_0$ tends to $t_k/k$ as the drift grows, where $t_k$ is the point at which the survival function of the Gamma$(k,1)$ distribution equals $e^{-1}$; for $k=4$ this limit is $1.0879\ldots$. The answer to the second question is yes, in continuous and in discrete time.
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.24069928
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint