Mathematics.

techniques

Coupling Methods

Probability50 minDifficulty7 out of 10

You should know: convergence in probability

Overview

A coupling is a joint construction of two or more random variables — possibly on different probability spaces or with different distributions — so that their relationship can be studied on a single probability space. Couplings are a powerful proof technique: to show that two distributions are 'close' or that one sequence converges to another, one constructs a coupling where the two variables are likely to be equal (or close), turning a statement about distributions into a statement about sample paths. Couplings are used to prove convergence of Markov chains, bound total variation distance, and establish stochastic ordering.

Intuition

A coupling answers: 'can I construct X ~ μ and Y ~ ν on the same probability space so that they are equal as often as possible?' If you can couple two Markov chains starting from different initial states so that they eventually occupy the same state, then after that 'meeting time' (the coupling time), both chains have the same distribution. The total variation distance between the two laws is bounded by the probability that the coupling has not yet succeeded — this is the coupling inequality. The approach converts a hard question about distributions into a tractable question about two particles on the same space.

Formal Definition

Definition

A coupling of two probability measures μ and ν on a measurable space (Ω, ℱ) is a pair of random variables (X, Y) defined on a common probability space such that X has distribution μ and Y has distribution ν. The coupling inequality is the key tool:

dTV(μ,ν)≤P(X≠Y)d_{\mathrm{TV}}(\mu, \nu) \leq P(X \neq Y)
Coupling inequality (total variation distance ≤ coupling probability)
dTV(μ,ν)=sup⁡A∣μ(A)−ν(A)∣=12∑x∣μ(x)−ν(x)∣d_{\mathrm{TV}}(\mu, \nu) = \sup_{A} |\mu(A) - \nu(A)| = \frac{1}{2}\sum_x |\mu(x) - \nu(x)|
Total variation distance (discrete case)
dTV(μ,ν)=min⁡(X,Y) couplingP(X≠Y)d_{\mathrm{TV}}(\mu, \nu) = \min_{(X,Y)\text{ coupling}} P(X \neq Y)
Optimal coupling achieves total variation distance

Worked Examples

  1. 1

    Construct a coupling: Let X ~ Poisson(λ) and let Z ~ Poisson(μ−λ) be independent of X. Set Y = X + Z.

    X∼Poisson⁡(λ),Z∼Poisson⁡(μ−λ),Y=X+Z∼Poisson⁡(μ)X \sim \operatorname{Poisson}(\lambda),\quad Z \sim \operatorname{Poisson}(\mu-\lambda),\quad Y = X + Z \sim \operatorname{Poisson}(\mu)
  2. 2

    In this coupling, X ≠ Y iff Z ≠ 0 (since Y = X + Z ≥ X, equality fails exactly when Z > 0).

    P(X≠Y)=P(Z≠0)=1−e−(μ−λ)P(X \neq Y) = P(Z \neq 0) = 1 - e^{-(\mu-\lambda)}
  3. 3

    Use the coupling inequality and the bound 1 − e^{−t} ≤ t for t ≥ 0.

    dTV(Poisson⁡(λ),Poisson⁡(μ))≤P(X≠Y)=1−e−(μ−λ)≤μ−λd_{\mathrm{TV}}(\operatorname{Poisson}(\lambda), \operatorname{Poisson}(\mu)) \leq P(X \neq Y) = 1 - e^{-(\mu-\lambda)} \leq \mu - \lambda

✓ Answer

d_TV(Poisson(λ), Poisson(μ)) ≤ μ − λ.

Practice Problems

Mediumfree response

State the coupling inequality and explain what it means intuitively.

Mediumfree response

Give an example of a maximal coupling and explain what makes it 'maximal'.

Quiz

A coupling of distributions μ and ν is:
The coupling inequality states:
In Markov chain mixing analysis, the coupling time T is used because:

Summary

  • A coupling is a joint construction of X ~ μ and Y ~ ν on a common probability space.
  • Coupling inequality: d_TV(μ, ν) ≤ P(X ≠ Y) for any coupling.
  • Maximal coupling achieves equality: P(X ≠ Y) = d_TV(μ, ν).
  • Couplings are used to prove Markov chain convergence, total variation bounds, and stochastic ordering.

References

  1. WebsiteWikipedia — Coupling (probability)