Quantitative bounds on convergence of time-inhomogeneous Markov chains

Randal Douc, Éric Moulines, Jeffrey S. RosenthalThe Annals of Applied Probability 2004 · DOI

TL;DR

This paper provides new, more general theoretical bounds on how quickly time-inhomogeneous Markov chains converge to their stationary distributions. The authors introduce a novel coupling-based approach that allows for "f-total variation" distance and handles chains whose transition probabilities change over time, a common scenario in applications like simulated annealing.

What Problem Does This Paper Address?

Understanding how fast a Markov chain "forgets" its initial state and settles into its long-term behavior is crucial in many fields, from statistical physics to machine learning. While theoretical tools exist to prove that a chain converges, getting precise quantitative bounds on the rate of convergence has been a significant challenge. Existing methods often provide bounds that are either too complex to use in practice or only apply to simpler cases, like time-homogeneous chains (where transition probabilities are constant over time). This paper tackles this by developing more general and explicit bounds for time-inhomogeneous chains, using a more flexible measure of convergence called "f-total variation distance."

Methods

The core of the paper's contribution lies in its novel application of coupling techniques to derive convergence bounds. Coupling involves constructing two versions of the Markov chain that start from different initial states and then observing when they "meet" or become identical. The time it takes for them to meet provides a direct measure of convergence.

Key methodological aspects include:

  • Generalizing Rosenthal's result: The authors extend a previous result by Rosenthal for time-homogeneous chains to the time-inhomogeneous setting.
  • f-Total Variation Distance: Instead of the standard total variation distance, they use an "f-total variation" distance, which is more flexible and can be applied with a wider range of functions f. This allows for finer-grained analysis.
  • (1,ε)-Coupling Sets: They introduce and utilize the concept of "(1,ε)-coupling sets" and related "pseudo-small" and "small" sets. These are technical conditions on the Markov chain's transition kernel that guarantee the existence of a coupling and are crucial for deriving the bounds.
  • Drift Conditions: The analysis relies on "drift conditions," which are inequalities that bound the expected change of a certain potential function V under the Markov chain's transitions. These conditions are essential for controlling the convergence rate.
  • Bivariate Analysis: For time-inhomogeneous chains, the coupling is performed on a product space (X x X), requiring the analysis of bivariate kernels and drift conditions.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on developing general mathematical bounds for Markov chains, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Flexibility of Coupling: The paper demonstrates the power of coupling as a versatile tool for deriving quantitative convergence rates, even for complex time-inhomogeneous chains.
  • f-Total Variation as a Powerful Metric: The use of f-total variation distance offers a more nuanced way to measure convergence compared to standard total variation, allowing for tighter bounds in certain scenarios.
  • Bridging Theory and Application: The paper explicitly connects theoretical advancements to practical problems like simulated annealing, showing how these new bounds can be applied.
  • General Conditions for Convergence: The introduction of (1,ε)-coupling sets and bivariate drift conditions provides a structured framework for analyzing a broader class of Markov chains.

Key Results

The paper presents several key theoretical results:

  • Theorem 2: Provides explicit bounds on the convergence rate for time-homogeneous Markov chains in f-total variation distance, improving upon existing work.
  • Theorem 8: Extends these bounds to time-inhomogeneous Markov chains, offering a general framework for analyzing chains with time-varying transition probabilities.
  • Proposition 3 & 4: Apply the general theorems to the specific case of convergence to stationarity, deriving bounds for total variation and f-norm.
  • Section 3 (Simulated Annealing): Demonstrates how the developed theory can be applied to analyze the convergence of simulated annealing algorithms, a widely used optimization technique. This includes deriving specific bounds for the convergence of simulated annealing.

The bounds are expressed in terms of parameters of the Markov chain, such as λ, ε, b, and B, which relate to the chain's mixing properties and the strength of the minorization and drift conditions.

Limitations and Future Work

  • Not Always Tight: The authors acknowledge that their bounds, while general and applicable, are not always "tight," meaning there might be room for improvement in the constants or the functional form of the bounds.
  • Assumptions: The derived bounds rely on specific technical assumptions (like the existence of (1,ε)-coupling sets and drift functions) that may not always be easy to verify for a given Markov chain.
  • Future Work: The paper suggests that further research could focus on refining these bounds, developing more practical methods for verifying the assumptions, and exploring applications to other areas where Markov chains are used. The example of simulated annealing hints at broader applicability to other optimization and sampling algorithms.

Summary updated

Abstract

Convergence rates of Markov chains have been widely studied in recent years. In particular, quantitative bounds on convergence rates have been studied in various forms by Meyn and Tweedie [Ann. Appl. Probab. 4 (1994) 981–1101], Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558–566], Roberts and Tweedie [Stochastic Process. Appl. 80 (1999) 211–229], Jones and Hobert [Statist. Sci. 16 (2001) 312–334] and Fort [Ph.D. thesis (2001) Univ. Paris VI]. In this paper, we extend a result of Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558–566] that concerns quantitative convergence rates for time-homogeneous Markov chains. Our extension allows us to consider f-total variation distance (instead of total variation) and time-inhomogeneous Markov chains. We apply our results to simulated annealing.
BibTeX
@article{douc2004quantitative,
  author = {Randal Douc and Éric Moulines and Jeffrey S. Rosenthal},
  title = {{Quantitative bounds on convergence of time-inhomogeneous Markov chains}},
  journal = {The Annals of Applied Probability},
  year = {2004},
  doi = {10.1214/105051604000000620},
}
Figure