In this post we will be looking at probabilistic coupling, which is putting two random variables (or proceses) on the same probability space. This turns out to be a surprisingly powerful tool in probability and this post will hopefully brainwash you into agreeing with me.
Consider first this baby problem. You and I flip coins and denote our -th coin flip. Suppose that I have probability of landing heads and you have probability of landing heads. Let
be the first times sees three heads in a row. Now obviously you know that , but can you prove it?
Of course here it is possible to compute both of the expectations and show this directly, but this is rather messy and long. Instead this will serve as a baby example of coupling.
So we want to put in the same probability space such that almost surely for each . Let be i.i.d. uniforms on and for each say that is heads if and otherwise tails, and is heads if and otherwise tails.
What is apparent here is that as we use the same source of “randomness”. Also the marginals are given by and hence
I really like this example of coupling because everyone learns this without learning coupling. We prove that using the transience of the simple symmetric random walk (SSRW) on , the SSRW on is transient for any . This is done by induction on so we will only look at .
Suppose is a random walk on and let be defined by projecting on to the first three co-ordinates, i.e. . Now this makes a lazy random walk on , to get rid of the laziness we define and
It is easy to see that almost surely and so is a random walk on .
Now one could make a contradiction argument here and say if was recurrent then would also be recurrent, but the construction here is hidden in that statement. Explicitly we constructed a random walk on and a random walk on such that
where denotes the Euclidian norm. Hence we have that if as , then so does .
So we suppose that is a bounded harmonic function. Liouville’s theorem states that is constant.
Let be a Brownian motion on and . It is easy to show that
Now we let be arbitrary and be the hyperplane such that reflected about it is . Define
Before we use coupling it is worth convincing yourself that . Loosely speaking, this is due to the fact that according the vector normal to , the Brownian motion is one dimensional.
Now we construct a new Brownian motion by reflecting about . This has the same law as . We see that
which holds for all , where . Taking and using the fact we see that the right hand side of the equation tends to zero.