has been known for quite some time; see the book-in-progress by Aldous and Fill, or the one by Pollard.

The relation

also seems to be folklore knowledge; I have not seen a proof anywhere and give a simple (non-probabilistic) one here (Lemma 2.6). Amir Dembo suggested that I re-derive this in a probability-theoretic way, via coupling. Here it is.

Recall that if and are probability measures on then

,

where the infimum is taken over all the distributions on , having marginals and , resp., and the random variables are and are distributed and . Any such joint measure on is called a

*coupling*and one achieving the infimum is called a

*maximal*coupling.

Applying this to our situation, let us define the random variables . Let be a maximal coupling of and , and define similarly for and . Notice that is a (not necessarily maximal) coupling of and . Then

.

## 1 comment:

Nice post, its a really cool blog that you have here, keep up the good work, will be back.

Warm Regards

Biby Cletus -

BlogPost a Comment