Subgeometric ergodicity of Markov chains

Randal Douc, Éric Moulines, Clément DombrySPIRE 2007 · DOI · arXiv

Abstract

This paper provides a short, self-contained proof of general bounds for subgeometric rates of convergence in Markov chains under practical conditions. By utilizing a coupling-based approach, the authors offer an intuitive understanding of the foundational results established by Nummelin and Tuominen (1983) and Tuominen and Tweedie (1994). To derive practical, computable rates, the framework incorporates a general drift condition recently introduced in Douc et al. (2004), bridging the gap between abstract existence proofs and applicable quantitative analysis.

Introduction

In the study of stochastic processes, particularly in applications like Markov Chain Monte Carlo (MCMC) and queueing theory, a fundamental question is the rate at which a Markov chain converges to its stationary distribution. While classical theory often focuses on "geometric ergodicity"—where the distance to equilibrium decays exponentially—many real-world systems exhibit "heavy-tailed" behavior. These systems converge at subgeometric rates, such as polynomial or logarithmic speeds.

Historically, while researchers proved that these slower rates existed, the proofs were frequently non-constructive. They established that a bound existed but did not provide the explicit constants necessary for practitioners to determine how long a simulation must run to reach a desired level of accuracy. This paper addresses this gap by providing a unified framework for calculating explicit, non-uniform bounds on subgeometric convergence.

Methodological Framework

The authors' approach rests on two primary mathematical pillars: coupling constructions and generalized drift conditions.

1. Coupling and the "Bell Variable"

Coupling is a probabilistic technique where two copies of a Markov chain are started from different initial distributions and forced to "meet" or couple. Once the chains meet, they remain together for all subsequent time steps. The time it takes for this coupling to occur directly determines the rate of convergence to the stationary distribution. The authors introduce a "bell variable" algorithmic approach, which makes the coupling process more mathematically tractable and provides an intuitive basis for the resulting bounds.

2. Generalized Drift Conditions

To make the convergence bounds computable, the paper employs a Lyapunov-style drift condition:

$$PV + \phi \circ V \le V + b \mathbb{1}_C$$

In this inequality:

  • $V$ is a Lyapunov function measuring the "distance" of the chain from the center of the state space.
  • $\phi$ is a function defining the "speed" of the return to a central set $C$.
  • $b$ is a constant, and $\mathbb{1}_C$ is the indicator function for the small set $C$.

By varying the shape of $\phi$ (for instance, making it concave), the authors can capture a wide spectrum of convergence regimes—from polynomial to subexponential—within a single theoretical framework.

Key Insights and Results

The Master Theorem Approach

Rather than offering fragmented proofs for different types of convergence, the paper presents a "Master Theorem" (Theorem 1). This theorem allows researchers to plug in a specific rate sequence, and the framework returns a corresponding bound. This unified theory simplifies the analysis of complex chains that do not fit the standard geometric mold.

Interpolation and Trade-offs

Using Young’s inequality, the authors demonstrate an "interpolation" strategy. This allows for a trade-off between the strength of the function $f$ being integrated and the rate of convergence $r$. This flexibility is crucial for researchers who may need to prioritize either the precision of the expectation or the speed of the convergence depending on the specific application.

Convergence Regimes

The paper provides explicit recipes for three primary subgeometric regimes:

  • Polynomial Rates: Occurring when the drift is relatively weak, leading to convergence rates like $n^{-\alpha}$.
  • Subexponential Rates: Bridging the gap between polynomial and geometric, covering rates like $\exp(cn^\delta)$.
  • Logarithmic Rates: Addressing extremely heavy-tailed distributions where convergence is exceptionally slow (e.g., $\log^\alpha(n)$).

Practical Implications and Limitations

Unlike previous theoretical work, the constants derived in this paper (such as $M$ and $W^*$) are defined in terms of hitting times and drift parameters. In principle, these can be calculated for specific models, providing a "guaranteed" safety margin for practitioners.

However, several challenges remain for real-world application:

  1. Small Set Identification: The bounds rely on the existence of a "small set" $C$ and a minorization constant $\epsilon$. In high-dimensional spaces, finding these sets and calculating $\epsilon$ is non-trivial.
  2. Lyapunov Function Selection: The framework requires a suitable drift function $V$. While the paper provides the framework, selecting the optimal $V$ for a new algorithm remains an "art" that requires deep domain knowledge.
  3. Conservatism: As with most theoretical upper bounds, the actual convergence of a Markov chain may be faster than the bound suggests. Nonetheless, these results provide a rigorous mathematical foundation for understanding the limits of subgeometric systems.

Summary updated

Abstract

The goal of this paper is to give a short and self contained proof of general bounds for subgeometric rates of convergence, under practical conditions. The main result whose proof, based on coupling, provides an intuitive understanding of the results of Nummelin and Tuominen (1983) and Tuominen and Tweedie (1994). To obtain practical rates, a very general drift condition, recently introduced in Douc et al (2004) is used.
BibTeX
@inproceedings{douc2007subgeometric,
  author = {Randal Douc and Éric Moulines and Clément Dombry},
  title = {{Subgeometric ergodicity of Markov chains}},
  booktitle = {SPIRE},
  year = {2007},
  doi = {10.48550/arxiv.0706.1837},
}
Figure