Let μ\mu and ν\nu be two probability measures over a finite set Ω\Omega.

Definition. A probability measure ω\omega over Ω×Ω\Omega \times \Omega is a coupling of (μ,ν)(\mu, \nu) if its marginals are μ\mu and ν\nu:

  1. ∀x∈Ω\forall x \in \Omega, ∑y∈Ωω(x,y)=μ(x)\sum_{y \in \Omega} \omega(x, y) = \mu(x),
  2. ∀y∈Ω\forall y \in \Omega, ∑x∈Ωω(x,y)=ν(y)\sum_{x \in \Omega} \omega(x, y) = \nu(y).

Coupling Lemma

Lemma

  1. For any coupling ω\omega of (μ,ν)(\mu, \nu), if the random variable (X,Y)(X, Y) is distributed according to ω\omega, then
Pr⁡[X≠Y]≥∥μ−ν∥TV. \Pr[ X \neq Y ] \ge \Vert \mu - \nu \Vert_{TV}.
  1. There exists a coupling ω∗\omega^* (which is called the maximal coupling) for (μ,ν)(\mu, \nu) for which
Pr⁡[X≠Y]=∥μ−ν∥TV. \Pr[ X \neq Y ] = \Vert \mu - \nu \Vert_{TV}.

First Proof

Claim 1. First, observe that for every measurable set S⊆ΩS \subseteq \Omega, it holds that

μ(S)−ν(S)=Pr⁡[X∈S]−Pr⁡[Y∈S]≤Pr⁡[X∈S,Y∉S]≤Pr⁡[X≠Y]. \begin{aligned} \mu(S) - \nu(S) = \Pr [ X \in S ] - \Pr [ Y \in S ] \le \Pr[ X \in S, Y \notin S ] \le \Pr[ X \neq Y ]. \end{aligned}

It follows that

∥μ−ν∥TV=max⁡ measurable S⊆Ω(μ(S)−ν(S))≤Pr⁡[X≠Y]. \Vert \mu - \nu \Vert_{TV} = \max_{ \text{ measurable } S \subseteq \Omega} \big( \mu(S) - \nu(S) \big) \le \Pr[ X \neq Y ].

Claim 2. Next, we show how to construct ω∗\omega^*. For each z∈Ωz \in \Omega, define

ω∗(z,z)=min⁡{μ(z),ν(z)}. \omega^*(z, z) = \min \{ \mu(z), \nu(z) \}.

Clearly it holds that

Pr⁡[X≠Y]=1−∑z∈Ωmin⁡{μ(z),ν(z)}=∥μ−ν∥TV. \begin{aligned} \Pr[ X \neq Y ] = 1 - \sum_{ z \in \Omega } \min \{ \mu(z), \nu(z) \} = \Vert \mu - \nu \Vert_{TV}. \end{aligned}

It is left to assign the probability mass ∥μ−ν∥TV\Vert \mu - \nu \Vert_{TV} to (x,y)∈Ω×Ω(x, y) \in \Omega \times \Omega, for x≠yx \neq y.

Case 1 (∥μ−ν∥TV=0)\big( \Vert \mu - \nu \Vert_{TV} = 0 \big). Then we can set ω∗(x,y)=0\omega^*(x, y) = 0 for all x≠yx \neq y. Further, it holds that μ(z)=ν(z)\mu(z) = \nu(z) for all z∈Ωz \in \Omega. Therefore,

∑y∈Ωw∗(x,y)=w∗(x,x)=min⁡{μ(x),ν(x)}=μ(x),∑x∈Ωw∗(x,y)=w∗(y,y)=min⁡{μ(y),ν(y)}=ν(y) . \begin{aligned} \sum_{ y \in \Omega } w^* (x, y) = w^*(x, x) = \min \{ \mu(x), \nu(x) \} = \mu( x ), \\ \sum_{ x \in \Omega } w^* (x, y) = w^*(y, y) = \min \{ \mu(y), \nu(y) \} = \nu( y )\,. \end{aligned}

Case 2 (∥μ−ν∥TV≠0)\big( \Vert \mu - \nu \Vert_{TV} \neq 0 \big). Denote S+≐{z∈Ω:μ(z)≥ν(z)}S_+ \doteq \{ z \in \Omega: \mu(z) \ge \nu(z) \}. Define two probability mass functions

λ1(z)≐μ(z)−ν(z)∥μ−ν∥TV⋅1[z∈S+],λ2(z)≐ν(z)−μ(z)∥μ−ν∥TV⋅1[z∉S+]. \lambda_1 (z) \doteq \frac{ \mu(z) - \nu(z) }{ \Vert \mu - \nu \Vert_{TV} } \cdot \mathbf{1}[z \in S_+],\qquad \lambda_2 (z) \doteq \frac{ \nu(z) - \mu(z) }{ \Vert \mu - \nu \Vert_{TV} } \cdot \mathbf{1}[z \notin S_+].

Then λ1(Ω)=λ1(S+)=λ2(Ω)=λ2(Sˉ+)=1\lambda_1 ( \Omega ) = \lambda_1 (S_+) = \lambda_2 (\Omega) = \lambda_2 ( \bar S_+ ) = 1.

Now, for x,y∈Ω,x≠yx, y \in \Omega, x \neq y, define

ω∗(x,y)=∥μ−ν∥TV⋅λ1(x)⋅λ2(y). \omega^*(x, y) = \Vert \mu - \nu \Vert_{TV} \cdot \lambda_1 (x) \cdot \lambda_2 (y) .

Also note that for all z∈Ωz \in \Omega, ∥μ−ν∥TV⋅λ1(z)⋅λ2(z)=0\Vert \mu - \nu \Vert_{TV} \cdot \lambda_1 (z) \cdot \lambda_2 (z) = 0. Therefore,

∑y∈Ωw∗(x,y)=w∗(x,x)+∑y∈Ω: y≠xw∗(x,y)=min⁡{μ(x),ν(x)}+∑y∈Ω∥μ−ν∥TV⋅λ1(x)⋅λ2(y)=min⁡{μ(x),ν(x)}+∥μ−ν∥TV⋅λ1(x)⋅λ2(Ω)=min⁡{μ(x),ν(x)}+(μ(x)−ν(x))⋅1[x∈S+]=μ(x). \begin{aligned} \sum_{ y \in \Omega } w^* (x, y) &= w^*(x, x) + \sum_{ y \in \Omega : \, y \neq x } w^* (x, y) \\ &= \min \{ \mu(x), \nu(x) \} + \sum_{ y \in \Omega } \Vert \mu - \nu \Vert_{TV} \cdot \lambda_1 (x) \cdot \lambda_2 (y) \\ &= \min \{ \mu(x), \nu(x) \} + \Vert \mu - \nu \Vert_{TV} \cdot \lambda_1 (x) \cdot \lambda_2 (\Omega) \\ &= \min \{ \mu(x), \nu(x) \} + \big( \mu(x) - \nu(x) \big) \cdot \mathbf{1}[x \in S_+] \\ &= \mu(x). \end{aligned}

Similarly, we can verify that for each y∈Ωy \in \Omega,

∑y∈Ωω∗(x,y)=ν(y). \sum_{y \in \Omega} \omega^*(x, y) = \nu(y).

□\square

Second Proof

Claim 1. We see that

Pr⁡[X=Y]=∑z∈ΩPr⁡[X=z,Y=z]≤∑z∈Ωmin⁡{μ(z),ν(z)}. \Pr[X = Y] = \sum_{z \in \Omega} \Pr[X = z, Y = z] \le \sum_{z \in \Omega} \min \{ \mu(z), \nu(z) \}.

Hence,

Pr⁡[X≠Y]=1−Pr⁡[X=Y]≥1−∑z∈Ωmin⁡{μ(z),ν(z)}=∑z∈Ω(μ(z)−min⁡{μ(z),ν(z)})=∥μ−ν∥TV. \begin{aligned} \Pr[X \neq Y] &= 1 - \Pr[X = Y] \ge 1 - \sum_{z \in \Omega} \min \{ \mu(z), \nu(z) \} \\ &= \sum_{z \in \Omega} \Big( \mu(z) - \min \{ \mu(z), \nu(z) \} \Big) = \Vert \mu - \nu \Vert_{TV}. \end{aligned}

Claim 2. The case is trivial if ∥μ−ν∥TV\Vert \mu - \nu \Vert_{TV}. Suppose that η=∥μ−ν∥TV>0\eta = \Vert \mu - \nu \Vert_{TV} > 0.

Define

λ(z)≐min⁡{μ(z),ν(z)},∀z∈Ω. \lambda(z) \doteq \min \{ \mu(z), \nu(z) \}, \qquad \forall z \in \Omega.

Further, define the distributions π0\pi_0 and π1\pi_1 by

π0(x,y)≐11−η⋅λ(x)⋅I[x=y],∀x,y∈Ω,π1(x,y)≐μ(x)−λ(x)η⋅ν(y)−λ(y)η∀x,y∈Ω. \begin{aligned} \pi_0 (x, y) &\doteq \frac{1}{1 - \eta} \cdot \lambda(x) \cdot \mathbb{I}{[x = y]}, & \forall x, y \in \Omega, \\ \pi_1 (x, y) &\doteq \frac{\mu(x) - \lambda(x)}{\eta} \cdot \frac{\nu(y) - \lambda(y)}{ \eta } & \forall x, y \in \Omega. \end{aligned}

Then π=(1−η)π0+ηπ1\pi = (1 - \eta) \pi_0 + \eta \pi_1 is a distribution, whose marginals are

∑y∈Ωπ(x,y)=λ(x)+(μ(x)−λ(x))=μ(x),∑x∈Ωπ(x,y)=λ(y)+(ν(y)−λ(y))=ν(y), \begin{aligned} \sum_{y \in \Omega} \pi(x, y) &= \lambda(x) + \big( \mu(x) - \lambda(x) \big) = \mu(x), \\ \sum_{x \in \Omega} \pi(x, y) &= \lambda(y) + \big( \nu(y) - \lambda(y) \big) = \nu(y), \end{aligned}

where we use the fact that

∥μ−ν∥TV=∑x∈Ω(μ(x)−λ(x))=∑y∈Ω(ν(y)−λ(y)). \Vert \mu - \nu \Vert_{TV} = \sum_{x \in \Omega} \big(\mu(x) - \lambda(x) \big) = \sum_{y \in \Omega} \big( \nu(y) - \lambda(y) \big).

Finally, consider the marginals of π0\pi_0 and π1\pi_1:

π0(x,⋅)≐∑y∈Ω11−η⋅λ(x)⋅I[x=y]=11−η⋅λ(x)∀x∈Ω,π0(⋅,y)≐∑x∈Ω11−η⋅λ(x)⋅I[x=y]=11−η⋅λ(y)∀y∈Ω,π1(x,⋅)≐∑y∈Ωμ(x)−λ(x)η⋅ν(y)−λ(y)η=μ(x)−λ(x)η∀x∈Ω,π1(⋅,y)≐∑x∈Ωμ(x)−λ(x)η⋅ν(y)−λ(y)η=ν(y)−λ(y)η∀y∈Ω, \begin{aligned} \pi_0 (x, \cdot) &\doteq \sum_{y \in \Omega} \frac{1}{1 - \eta} \cdot \lambda(x) \cdot \mathbb{I}{[x = y]} = \frac{1}{1 - \eta} \cdot \lambda(x) & \forall x \in \Omega, \\ \pi_0 (\cdot, y) &\doteq \sum_{x \in \Omega} \frac{1}{1 - \eta} \cdot \lambda(x) \cdot \mathbb{I}{[x = y]} = \frac{1}{1 - \eta} \cdot \lambda(y) & \forall y \in \Omega, \\ \pi_1 (x, \cdot) &\doteq \sum_{y \in \Omega} \frac{\mu(x) - \lambda(x)}{\eta} \cdot \frac{\nu(y) - \lambda(y)}{ \eta } = \frac{\mu(x) - \lambda(x)}{\eta} & \forall x \in \Omega, \\ \pi_1 (\cdot, y) &\doteq \sum_{x \in \Omega} \frac{\mu(x) - \lambda(x)}{\eta} \cdot \frac{\nu(y) - \lambda(y)}{ \eta } = \frac{\nu(y) - \lambda(y)}{ \eta } & \forall y \in \Omega, \end{aligned}

Then π1(x,⋅)\pi_1 (x, \cdot) and π1(⋅,y)\pi_1 (\cdot, y) have disjoint support, and η\eta is the minimum parameter such that the following condition hold:

μ=(1−η)⋅π0(x,⋅)+η⋅π1(x,⋅),ν=(1−η)⋅π0(⋅,y)+η⋅π1(⋅,y). \mu = (1 - \eta) \cdot \pi_0 (x, \cdot) + \eta \cdot \pi_1 (x, \cdot), \\ \nu = (1 - \eta) \cdot \pi_0 (\cdot, y) + \eta \cdot \pi_1 (\cdot, y).

□\square

Reference

[1] Constantinos Daskalakis, 6.896 Probability and Computation, Lecture 3, 2011.