Computable Bounds for Geometric Convergence Rates of Markov Chains

TLDR

Geometric ergodicity of Markov chains guarantees constants \(R<\infty\) and \(\rho<1\) such that the distance to stationarity decays as \(R\,V(x)\,\rho^n\), with \(V\) satisfying the standard drift inequality. This work derives explicit computable bounds for \(R\) and \(\rho\) in terms of the drift parameters \(\lambda\), \(b\) and the minorization constants that certify the small set \(C\). By expressing \(\rho\) as any value exceeding a threshold \(\vartheta\) defined through \(\lambda\), \(b\), \(\delta\) and the minorizing constants, and setting \(R\le \rho/(\rho-\vartheta)\), the authors provide closed‑form formulas for both bounds, with analogous but more involved expressions for general small sets. The bounds are illustrated on simple queueing models and on a Markov chain Monte Carlo algorithm, where they hold but are too loose for practical use in the latter case.

Abstract

Recent results for geometrically ergodic Markov chains show that there exist constants $R < \infty, \rho < 1$ such that $\sup_{|f|\leq V}\big|\int P^n(x, dy)f(y) - \int \pi(dy)f(y)\big| \leq RV(x)\rho^n,$ where $\pi$ is the invariant probability measure and $V$ is any solution of the drift inequalities $\int P(x, dy)V(y) \leq \lambda V(x) + b \mathbb{l}_C(x),$ which are known to guarantee geometric convergence for $\lambda < 1, b < \infty$ and a suitable small set $C$. In this paper we identify for the first time computable bounds on $R$ and $\rho$ in terms of $\lambda, b$ and the minorizing constants which guarantee the smallness of $C$. In the simplest case where $C$ is an atom $\alpha$ with $P(\alpha, \alpha) \geq \delta$ we can choose any $\rho > \vartheta$, where $\lbrack 1 - \vartheta\rbrack^{-1} = \frac{1}{(1 - \lambda)^2} \lbrack 1 - \lambda + b + b^2 + \zeta_\alpha(b(1 - \lambda) + b^2)\rbrack$ and $\zeta_\alpha \leq \big(\frac{32 - 8 \delta^2}{\delta^3}\big) \big(\frac{b}{1 - \lambda}\big)^2,$ and we can then choose $R \leq \rho/(\rho - \vartheta)$. The bounds for general small sets $C$ are similar but more complex. We apply these to simple queuing models and Markov chain Monte Carlo algorithms, although in the latter the bounds are clearly too large for practical application in the case considered.