Nice examples/arguments that illustrating the coupling method in probability theory

Question

I want some examples that can best illustrate the idea/power/funny of the coupling argument in probability. I think arguments with coupling makes one think in a more probabulistic way. I have a short list of simple examples, but of course there must be more and more.

To number a few examples I can recall:

1. Proof of the convergence to stationary measure in Markov chain theory, this is now the "classical" way followed by most text books.

2. Dynkin's card trick. See page 312 on Durrett's book "probability: theory and examples".

3. Percolation theory: every edge in the lattice graph $\mathbb{Z}^2$ is connected with probability $p$ or disconnected with parobability $1-p$ (independently). Then the measure of the event {there is a path from the origin to infinity} is an increasing function of $p$.

My question is: are there more examples?

Answer 1

This is similar to Anthony Quas's answer but maybe even simpler. Let $X_n$ be a Binomial random variable with probability $p$ and $n$ trials.

Then $P(X_n > k)$ is an increasing function of $n$.

Writing out the formula directly is surprisingly messy. But a coupling argument is easy: derive $X_n$ from $X_{n+1}$ by removing the first element.

Answer 2

There are plenty. For example one can show Liouville's theorem using a coupling argument (it is in Rogers&Williams second volume and here: http://blameitontheanalyst.wordpress.com/2012/01/24/probabilistic-coupling/).

On the other hand if you are looking for original results proved using coupling arguments then have a look at: http://arxiv.org/abs/math/0404356. Roughly speaking, Schramm uses a coupling argument to show that large cycles of the transposition random walk are "well mixed" after $cn/2$ time where $c>1$.

Answer 3

In percolation, there is a simple proof that $p_c^{site} \geq p_c^{bond}$ on any graph, by coupling an exploration of the cluster of a point.

Answer 4

One of the deepest and most beautiful coupling arguments I have seen is the proof by Moser and Tardos of their Algorithmic Local Lemma.

This algorithm tries to find a good configuration of variables by repeatedly resampling variables. Which groups of variables to resample can depend in a complicated way on the previous state of the stochastic system.

Their proof uses a coupling argument: before resampling any variables, you choose an infinite table of values for all variables, listing all the future resamplings. When you resample a variable, you always take the next choice in your table.

Their proof then derives necessary conditions on this table of values, and this shows that their algorithm works regardless of which groups of variables one chooses to resample

Answer 5

Here's an argument that I really like. I think it's not easy without coupling. Imagine a infinite ladder with rungs labelled by the positive integers. You perform a Markov chain. If you're in state $n$, either you move up the ladder (move to state $n+1$) with probability $1-p_n$, or you fall off (move to state 0) with probability $p_n$.

As you get higher, you're more careful so that $p_n$ is a decreasing sequence.

Claim: $\mathbb P(X_n>k | X_0=j)$ is an increasing function of $j$.

Proof: Use couplings.