Proof for total variation distance for product measure using coupling 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?
 A: There are two parts to the Coupling Lemma:
If $\mu$ and $\nu$ are two probability measures over a finite set $\Omega$, then:


*

*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)$$

*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}$$
