Coupling (probability)

Coupling is a technique in probability theory used to compare and analyze different stochastic processes by constructing them on a common probability space. This construction allows one to directly compare the sample paths of the processes and, under favorable circumstances, prove convergence or establish bounds on the distance between their distributions. The central idea is to link or "couple" the evolution of two or more random processes in such a way that their dependence can be exploited to reveal information about their individual behaviors.

The power of coupling lies in its ability to replace distributional comparisons with pathwise comparisons. Instead of arguing about probabilities and expectations, coupling aims to show that the processes become "close" or "equal" at some point in time with high probability. The notion of "closeness" is problem-specific and depends on the distance measure being used.

A successful coupling argument often involves designing a joint evolution rule for the coupled processes. This rule dictates how the processes evolve simultaneously, ensuring that they remain related in a meaningful way. Key to the design is achieving a coupling time, which is the time it takes for the processes to become identical or sufficiently close according to the chosen distance measure. Bounding the expectation or distribution of the coupling time then provides information about the rate of convergence or the distance between the distributions of the processes.

Applications of coupling are wide-ranging, including:

• Markov chain Monte Carlo (MCMC): Analyzing the convergence of MCMC algorithms by coupling chains started from different initial states.
• Percolation theory: Studying the connectivity properties of random graphs and networks.
• Queueing theory: Analyzing the stability and performance of queueing systems.
• Statistical physics: Understanding phase transitions and critical phenomena.
• Probability on groups: Studying the rate of convergence of random walks on groups.

Different types of coupling exist, including:

• Maximal coupling: Aims to maximize the probability that the coupled processes meet at a given time.
• Monotone coupling: Used for processes with a natural ordering, where the coupling preserves this ordering.
• Common random numbers: Uses the same random numbers to drive the evolution of different processes.

The choice of coupling method depends on the specific problem and the properties of the stochastic processes being analyzed. A clever choice of coupling can often lead to elegant and powerful results.