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