2
$\begingroup$

If $\mu_1$ and $\nu_1$ are probability distributions on the finite state space $\Omega_1$, $\mu_2$ and $\nu_2$ are probability distributions on the finite state space $\Omega_2$, $\mu_1 \times \mu_2 (x,y) = \mu_1(x)\mu_2(y)$ and $\nu_1 \times \nu_2 (x,y) = \nu_1(x)\nu_2(y)$ are probability measures on $\Omega_1 \times \Omega_2$.

It follows from the triangle inequality that

$$\|\mu_1\times\mu_2 - \nu_1\times\nu_2 \|_{TV} \leq \|\mu_1-\nu_1\|_{TV}+\|\mu_2-\nu_2\|_{TV}$$

I heard it mentioned in a few places that this can also be proved using coupling, but could not figure that. Could someone walk me through or point me to the proof?

$\endgroup$
  • 1
    $\begingroup$ Proof: If $X=(X_1,X_2)$ and $Y=(Y_1,Y_2)$, then $$P(X\ne Y)\leqslant P(X_1\ne Y_1)+P(X_2\ne Y_2)$$ End of the proof. $\endgroup$ – Did Apr 10 '18 at 16:31
  • $\begingroup$ But $P(X_1 \neq Y_1) \geq \|\mu_1 - \nu_1\|$. So how can I get that $P(X\neq Y) \leq \|\mu_1 - \nu_1\| + \|\mu_2 - \nu_2\|$ from this? $\endgroup$ – The Hagen Apr 10 '18 at 17:05
  • 2
    $\begingroup$ By considering the infima of the probabilities $P(X_i\ne Y_i)$ on the couples $(X_i,Y_i)$ with the correct marginals. $\endgroup$ – Did Apr 10 '18 at 19:01
  • $\begingroup$ Thanks! Why post this as a comment? It answered my question $\endgroup$ – The Hagen Apr 10 '18 at 19:13
  • $\begingroup$ To let you the opportunity to expand these hints into a full-fledged answer, which you would then post it here. $\endgroup$ – Did Apr 10 '18 at 19:15
2
$\begingroup$

There are two parts to the Coupling Lemma:

If $\mu$ and $\nu$ are two probability measures over a finite set $\Omega$, then:

  1. For any coupling $\omega$ of $(\mu,\nu)$, if the random variable $(X,Y)$ is distributed according to $\omega$, then $$\|\mu-\nu\|_{TV} \leq P(X\neq Y)$$

  2. There exists an optimal coupling $\omega^*$ of $(\mu,\nu)$ for which $$\|\mu-\nu\|_{TV} = P(X\neq Y)$$

Picking $\omega_1^*$ as the optimal coupling on $(\mu_1, \nu_1)$, and $\omega_2^*$ as the optimal coupling on $(\mu_2, \nu_2)$, take the random variable $(X_1, Y_1)$ distributed according to $\omega_1^*$ and $(X_2, Y_2)$ distributed according to $\omega_2^*$, we have

$$P(X_1\neq Y_1) + P(X_2\neq Y_2) = \|\mu_1-\nu_1\|_{TV} + \|\mu_2-\nu_2\|_{TV}$$

by part 2.

Defining $X=(X_1,X_2)$, $Y=(Y_1,Y_2)$, we further have that

$$P(X\neq Y) = 1-P(X=Y) = 1-P(X_1=Y_1)P(X_2=Y_2) \leq 1-P(X_1=Y_1) + 1-P(X_2=Y_2) = P(X_1\neq Y_1) + P(X_2\neq Y_2)$$

where the inequality comes from the fact that for $0\leq a, b, \leq 1$:

$$a(1-b)\leq 1- b \Rightarrow a-ab\leq 1-b \Rightarrow -ab\leq 1-(a+b) \Rightarrow 1-ab \leq (1-a) + (1-b)$$

and noting that the law of $(X,Y)$ is a coupling of $(\mu_1\times\mu2, \nu_1\times\nu2)$, by part 1 we are done:

$$\|\mu_1\times\mu2 - \nu_1\times\nu2\|_{TV} \leq P(X\neq Y) \leq P(X_1\neq Y_1) + P(X_2\neq Y_2) = \|\mu_1-\nu_1\|_{TV} + \|\mu_2-\nu_2\|_{TV}$$

$\endgroup$
  • $\begingroup$ Why is the (X;Y) a coupling of $(\mu, \nu)$? We do not know that $X_1$ and $X_2$ are independent. $\endgroup$ – franzk Nov 4 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.