# Minimal coupling

Let $$\mu,\nu$$ be probability measures defined on a common measure space $$(\Omega,\mathcal F)$$. A coupling of $$\mu,\nu$$ is a probability measure $$\pi$$ on $$(\Omega^2,\mathcal F^2)$$ with marginals $$\mu,\nu$$ respectively. Let $$\Delta\subseteq \Omega^2$$ denote the diagonal, $$\Delta=\{(\omega,\omega)\colon \omega\in \Omega^2\}$$. It is well-known (and not difficult to verify) that every coupling $$\pi$$ satisfies the inequality $$\pi(\Delta)\leq 1-\|\mu-\nu\|_{TV},$$ where $$\|\mu-\nu\|_{TV}:=\sup_{A\in \mathcal F}|\mu(A)-\nu(A)|$$, and it is also not difficult to construct a coupling attaining the equality (i.e. constructing a maximal coupling).

My question concerns minimal couplings: is there a non-trivial lower bound on $$\pi(\Delta)$$, and if so, is there a simple construction attaining this lower bound for all probability measures $$\mu,\nu$$?

The question is less interesting in the non-atomic case, since the independent coupling would already assign no mass to the diagonal. Also, if singletons are measurable, then there is an easy lower bound of $$\pi(\{(x,x)\})\geq \bigl(\mu(\{x\})+\nu(\{x\})-1\bigr)_+$$, from which one can derive a lower bound on $$\pi(\Delta)$$ in the completely atomic case. Is this bound optimal? Under what conditions on $$\mu,\nu$$ does there exist a coupling with $$\pi(\Delta)=0$$?

## 2 Answers

The lower bound $$\sum_x (\mu(\{x\}) = \nu(\{x\}) - 1)_+$$ is indeed optimal (and only one of the summands can possibly be non-zero). This is easily proved, but somewhat tedious to type; let me give an intuitive explanation instead.

Imagine $$n$$ people ("atoms") sitting around a table, the $$i$$-th person having $$\mu(\{x_i\})$$ coins of different colours stacked in front of them.

• In the initial round each person moves their stack to the right.
• In each of the successive rounds the $$i$$-th person checks if they have more then $$\nu(\{x_i\})$$ coins. If yes, they take the exceeding amount of coins from the bottom of their stack, and move it to the top of the stack of their right neighbour.

This is played until each person has the desired amount of money. It can be checked that $$i$$-th person got some of their coins back if and only if $$\mu(\{x_i\}) + \nu(\{x_i\}) > 1$$. Now $$\pi(\{x_i,x_j\}) = \text{numer of coins of i-th colour in j-th stack}$$ is the desired coupling.

This also works when there are infinitely many atoms if you allow for infinitely many rounds.

• Looks like Bjørn Kjos-Hanssen not only was faster, but also gave a nicer solution. Anyway, I think I'll leave this answer here. – Mateusz Kwaśnicki Sep 17 '19 at 8:15

Yes, your bound is optimal and here's how to attain it.

Fix a linear ordering $$L$$ of $$\Omega$$. Pick a number $$x \in [0,1]$$ under the uniform measure and the value of our coupling shall be $$(M(x),N(x))$$.

Let $$M(x)\in \Omega$$ be the $$L$$-greatest $$a$$ such that $$\mu(\{c\in \Omega: c\le_L a\}\le x.$$

Let $$N(x)\in \Omega$$ be the $$L$$-greatest $$a$$ such that $$\mu(\{c\in \Omega: c\le_L a\}\le x+\frac12\mod 1.$$

This makes $$\pi(\Delta)=0$$ unless there is a single outcome whose $$\mu+\nu>1$$, by the way.

I suppose there could be some measurability concerns about $$L$$ but at least it works in the cases of discrete, or continuous real-valued, random variables.