Extremal couplings

This post is inspired by an assignment question I had to answer for STATS 310A – a probability course at Stanford for first year students in the statistics PhD program. In the question we had to derive a few results about couplings. I found myself thinking and talking about the question long after submitting the assignment and decided to put my thoughts on paper. I would like to thank our lecturer Prof. Diaconis for answering my questions and pointing me in the right direction.

What are couplings?

Given two distribution functions F and G on \mathbb{R}, a coupling of F and G is a distribution function H on \mathbb{R}^2 such that the marginals of H are F and G. Couplings can be used to give probabilistic proofs of analytic statements about F and G (see here). Couplings are also are studied in their own right in the theory optimal transport.

We can think of F and G as being the cumulative distribution functions of some random variables X and Y. A coupling H of F and G thus corresponds to a random vector (\widetilde{X},\widetilde{Y}) where \widetilde{X} has the same distribution as X, \widetilde{Y} has the same distribution as Y and (\widetilde{X},\widetilde{Y})  \sim H.

The independent coupling

For two given distributions function F and G there exist many possible couplings. For example we could take H = H_I where H_I(x,y) = F(x)G(y). This coupling corresponds to a random vector (\widetilde{X}_I,\widetilde{Y}_I) where \widetilde{X}_I and \widetilde{Y}_I are independent and (as is required for all couplings) \widetilde{X}_I \stackrel{\text{dist}}{=} X, \widetilde{Y}_I \stackrel{\text{dist}}{=} Y.

In some sense the coupling H_I is in the “middle” of all couplings. This is because \widetilde{X} and \widetilde{Y} are independent and so \widetilde{X} doesn’t carry any information about \widetilde{Y}. As the title of the post suggests, there are couplings were this isn’t the case and \widetilde{X} carries “as much information as possible” about \widetilde{Y}.

The two extremal couplings

Define two function H_L, H_U :\mathbb{R}^2 \to [0,1] by

H_U(x,y) = \min\{F(x), G(y)\} and H_L(x,y) = \max\{F(x)+G(y) - 1, 0\}.

With some work, one can show that H_L and H_U are distributions functions on \mathbb{R}^2 and that they have the correct marginals. In this post I would like to talk about how to construct random vectors (\widetilde{X}_U, \widetilde{Y}_U) \sim H_U and (\widetilde{X}_L, \widetilde{Y}_L) \sim H_L.

Let F^{-1} and G^{-1} be the quantile functions of F and G. That is,

F^{-1}(c) = \inf\{ x \in \mathbb{R} : F(x) \ge c\} and G^{-1}(c) = \inf\{ x \in \mathbb{R} : G(x) \ge c\}.

Now let V be a random variable that is uniformly distributed on [0,1] and define

\widetilde{X}_U = F^{-1}(V) and \widetilde{Y}_U = G^{-1}(V).

Since F^{-1}(V) \le x if and only if V \le F(x), we have \widetilde{X}_U \stackrel{\text{dist}}{=} X and likewise \widetilde{Y}_U \stackrel{\text{dist}}{=} Y. Furthermore \widetilde{X}_U \le x, \widetilde{Y}_U \le y occurs if and only if V \le F(x), V \le G(y) which is equivalent to V \le \min\{F(x),G(y)\}. Thus

\mathbb{P}(\widetilde{X}_U \le x, \widetilde{Y}_U \le y) = \mathbb{P}(V \le \min\{F(x),G(y)\})= \min\{F(x),G(y)\}.

Thus (\widetilde{X}_U,\widetilde{Y}_U) is distributed according to H_U. We see that under the coupling H_U, \widetilde{X}_U and \widetilde{Y}_U are closely related as they are both increasing functions of a common random variable V.

We can follow a similar construction for H_L. Define

\widetilde{X}_L = F^{-1}(V) and \widetilde{Y}_L = G^{-1}(1-V).

Thus \widetilde{X}_L and \widetilde{Y}_L are again functions of a common random variable V but \widetilde{X}_L is an increasing function of V and \widetilde{Y}_L is a decreasing function of V. Note that 1-V is also uniformly distributed on [0,1]. Thus \widetilde{X}_L \stackrel{\text{dist}}{=} X and \widetilde{Y}_L \stackrel{\text{dist}}{=} Y.

Now \widetilde{X}_L \le x, \widetilde{Y}_L \le y occurs if and only if V \le F(x) and 1-V \le G(y) which occurs if and only if 1-G(y) \le V \le F(x). If 1-G(y) \le F(x), then F(x)+G(y)-1 \ge 0 and \mathbb{P}(1-G(y) \le V \le F(x)) =F(x)+G(y)-1. On the other hand, if 1 - G(y) > F(x), then F(x)+G(y)-1< 0 and \mathbb{P}(1-G(y) \le V \le F(x))=0. Thus

\mathbb{P}(\widetilde{X}_L \le x, \widetilde{Y}_L \le y) = \mathbb{P}(1-G(y) \le V \le F(x)) = \max\{F(x)+G(y)-1,0\},

and so (\widetilde{X}_L,\widetilde{Y}_L) is distributed according to H_L.

What makes H_U and H_L extreme?

Now that we know that H_U and H_L are indeed couplings, it is natural to ask what makes them “extreme”. What we would like to say is that \widetilde{Y}_U is an increasing function of \widetilde{X}_U and \widetilde{Y}_L is a decreasing function of \widetilde{X}_L. Unfortunately this isn’t always the case as can be seen by taking X to be constant and Y to be continuous.

However the intuition that \widetilde{Y}_U is increasing in \widetilde{X}_U and \widetilde{Y}_L is decreasing in \widetilde{X}_L is close to correct. Given a coupling (\widetilde{X},\widetilde{Y}) \sim H, we can look at the quantity

C(x,y) = \mathbb{P}(\widetilde{Y} \le y | \widetilde{X} \le x) -\mathbb{P}(\widetilde{Y} \le y) = \frac{H(x,y)}{F(x)}-G(y)

This quantity tells us something about how \widetilde{Y} changes with \widetilde{X}. For instance if \widetilde{X} and \widetilde{Y} were positively correlated, then C(x,y) would be positive and if \widetilde{X} and \widetilde{Y} were negatively correlated, then C(x,y) would be negative.

For the independent coupling (\widetilde{X}_I,\widetilde{Y}_I) \sim H_I, the quantity C(x,y) is constantly 0. It turns out that the above probability is maximised by the coupling (\widetilde{X}_U, \widetilde{Y}_U) \sim H_U and minimised by (\widetilde{X}_L,\widetilde{Y}_L) \sim H_L and it is in this sense that they are extremal. This final claim is the two dimensional version of the Fréchet-Hoeffding Theorem and checking it is a good exercise.

One thought on “Extremal couplings”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s