In probability theory, coupling is a proof technique that allows one to compare two unrelated random variables (distributions) X and Y by creating a random vector W whose marginal distributions correspond to X and Y respectively.
be two random variables defined on probability spaces
Assume two particles A and B perform a simple random walk in two dimensions, but they start from different points.
The simplest way to couple them is simply to force them to walk together.
On every step, if A walks up, so does B, if A moves to the left, so does B, etc.
Thus, the difference between the two particles' positions stays fixed.
As far as A is concerned, it is doing a perfect random walk, while B is the copycat.
B holds the opposite view, i.e. that it is, in effect, the original and that A is the copy.
First couple them so that they walk together in the vertical direction, i.e. if A goes up, so does B, etc., but are mirror images in the horizontal direction i.e. if A goes left, B goes right and vice versa.
We continue this coupling until A and B have the same horizontal coordinate, or in other words are on the vertical line (5,y).
If they never meet, we continue this process forever (the probability of that is zero, though).
We continue this rule until they meet in the vertical direction too (if they do), and from that point on, we just let them walk together.
Each particle performs a simple random walk.
And yet, our coupling rule forces them to meet almost surely and to continue from that point on together permanently.
This allows one to prove many interesting results that say that "in the long run", it is not important where you started in order to obtain that particular result.
Assume two biased coins, the first with probability p of turning up heads and the second with probability q > p of turning up heads.
Intuitively, if both coins are tossed the same number of times, we should expect the first coin turns up fewer heads than the second one.
More specifically, for any fixed k, the probability that the first coin produces at least k heads should be less than the probability that the second coin produces at least k heads.
However proving such a fact can be difficult with a standard counting argument.
Let X1, X2, ..., Xn be indicator variables for heads in a sequence of flips of the first coin.
For the second coin, define a new sequence Y1, Y2, ..., Yn such that Then the sequence of Yi has exactly the probability distribution of tosses made with the second coin.
As you let time run these two processes will evolve independently.