Subgeometric ergodicity of Markov chains

Randal Douc, Eric Moulines, Philippe SoulierLecture Notes in Statistics 2006 · DOI · arXiv · OpenAlex

This 2007 paper by Douc, Moulines, and Soulier provides a rigorous yet accessible framework for calculating exactly how fast a Markov chain settles into its steady state when that process happens slower than exponentially. By combining coupling techniques with generalized "drift conditions," the authors offer a unified way to derive computable bounds for polynomial, logarithmic, and subexponential convergence rates.

TL;DR

The paper provides explicit, computable bounds for the rate at which Markov chains converge to their stationary distribution in cases where convergence is "subgeometric" (slower than exponential). It bridges a gap in the literature by moving from purely theoretical existence proofs to practical formulas that can be applied to MCMC algorithms and queueing models.

What Problem Does This Paper Address?

In fields like statistics (MCMC methods) and operations research (queueing theory), we often use Markov chains to model complex systems. A critical question is: How long do we have to wait before the chain is "close enough" to its stationary distribution?

For many "well-behaved" chains, this convergence happens geometrically (exponentially fast). However, many practical models—especially those with heavy-tailed distributions or complex constraints—converge much more slowly. While mathematicians have known these "subgeometric" rates exist for decades, they often lacked quantitative bounds. In other words, we knew the chain converged at a certain rate, but we couldn't easily calculate a specific number of steps required. This paper aims to provide those explicit, computable formulas.

Methods

The authors employ two primary mathematical tools to build their bounds:

  1. Coupling Techniques: This involves constructing a "bivariate" Markov chain—essentially running two copies of the chain simultaneously. One copy starts at a fixed point, and the other starts at the stationary distribution. By measuring the "hitting time" (the time it takes for these two copies to meet or "couple"), the authors can bound the distance between the chain's current state and its steady state.
  2. Generalized Drift Conditions: The authors use a Lyapunov-like function $V$ (a "control function") and a concave function $\phi$ to describe how the chain moves toward the center of the state space. The condition $PV + \phi \circ V \leq V + b\mathbb{1}_C$ essentially says that when the chain is outside a "small set" $C$, it tends to drift back toward $C$ at a rate governed by $\phi$.
  3. Young’s Inequality for Interpolation: To handle different types of convergence (e.g., total variation vs. $f$-norm), the authors use interpolation techniques to trade off the strength of the convergence rate against the "weight" of the function being measured.

Datasets

Not discussed in the paper. This is a theoretical probability paper focused on proving theorems and providing mathematical frameworks; it does not use empirical datasets or benchmarks.

Key Insights and Ideas

  • The Power of Concavity: By using a concave function $\phi$ in the drift condition, the authors can capture a wide spectrum of convergence behaviors. If $\phi$ is linear, you get geometric convergence; if $\phi$ grows more slowly (like a power or a log), you get subgeometric rates.
  • Computability is Key: Unlike previous work that relied on abstract constants, the bounds in Theorem 1 and Proposition 1 are expressed in terms of parameters that can actually be calculated for a given transition kernel (like the "small set" constant $\epsilon$ and the drift parameters $b$ and $\lambda$).
  • The "Bell Variable": The proof utilizes a clever "split chain" construction where a binary variable $d_n$ acts as a signal for whether coupling has occurred, simplifying the tracking of the convergence process.

Key Results

The paper provides a "menu" of convergence rates based on the choice of the drift function $\phi$:

  • Polynomial Rates: If the drift is proportional to a power of the Lyapunov function ($\phi(v) \propto v^\alpha$), the chain converges at a polynomial rate $O(n^{-\alpha/(1-\alpha)})$.
  • Logarithmic Rates: If the drift is very weak (logarithmic), the convergence is similarly slow, following $O(\log^\alpha(n))$.
  • Subexponential Rates: For intermediate cases (e.g., $\phi(v) \propto v/\log^\alpha(v)$), the authors derive rates that are faster than any polynomial but slower than geometric, such as $O(\exp(n^{1/(1+\alpha)}))$.

Theorem 1 stands as the central result, providing a general inequality that bounds the sum of the weighted distances between the chain and its stationary distribution.

Limitations and Future Work

  • Small Set Dependency: The entire framework relies on Assumption (A1): the existence of a "small set" $C$. In high-dimensional or very complex state spaces, identifying such a set and calculating its minorization constant $\epsilon$ can be extremely difficult.
  • Tightness of Bounds: While the bounds are explicit, the authors acknowledge that they may not always be "tight." There is often a trade-off between the size of the small set and the constants in the bound, which requires careful tuning for practical applications.
  • Extension to $m$-step Minorization: The paper primarily focuses on one-step minorization for simplicity. While they mention that extensions to $m$-step minorization are possible, the formulas would become significantly more complex.

Summary updated

BibTeX
@inproceedings{douc2006subgeometric,
  author = {Randal Douc and Eric Moulines and Philippe Soulier},
  title = {{Subgeometric ergodicity of Markov chains}},
  booktitle = {Lecture Notes in Statistics},
  year = {2006},
  doi = {10.1007/0-387-36062-x\_2},
}
Figure