Total variation distance of two random vectors whose components are independent Let $X^n=\left(X_1,\ldots,X_n \right)$ and $Y^n=\left(Y_1,\ldots,Y_n \right)$ be such that all $X_i$'s are independent and all $Y_i$'s are independent. I am trying to prove the following:
$$
d_{TV} \left(\mathbb{P}_{X^n},\mathbb{P}_{Y^n} \right) \leq \sum_{i=1}^n d_{TV} \left( \mathbb{P}_{X_i},\mathbb{P}_{Y_i} \right).
$$
Can anyone help me how to start ? Or provide a useful hint to proceed in the right direction ?
 A: For simplicity (and WOLG), assume $n = 2$, and let $\mu_1, \mu_2$ be distributions of $X_1$ and $X_2$, $\nu_1, \nu_2$ be distributions of $Y_1$ and $Y_2$. By independence assumption, $(X_1, X_2)$ and $(Y_1, Y_2)$ have product measures $\mu_1 \times \mu_2$ and $\nu_1 \times \nu_2$ respectively.
For any $A \in \mathscr{R^2}$, we have 
\begin{align}
& |(\mu_1 \times \mu_2)(A) - (\nu_1 \times \nu_2)(A) | \\
= & \left|\int_\mathbb{R} \mu_2(A_x) \mu_1(dx) - \int_\mathbb{R} \nu_2(A_x) \nu_1(dx)\right| \\
= & \left|\int_\mathbb{R} \mu_2(A_x) \mu_1(dx) -  
\int_\mathbb{R} \nu_2(A_x) \mu_1(dx) + 
\int_\mathbb{R} \nu_2(A_x) \mu_1(dx) - 
\int_\mathbb{R} \nu_2(A_x) \nu_1(dx)\right| \\
\leq & \int_\mathbb{R} |\mu_2(A_x) - \nu_2(A_x)| \mu_1(dx) + 
\left|\int_\mathbb{R} \nu_2(A_x) \mu_1(dx) - 
\int_\mathbb{R} \nu_2(A_x) \nu_1(dx)\right| \\ 
\leq & d_{TV}(\mu_2, \nu_2) + \left|\int_\mathbb{R} \mu_1(A_y) \nu_2(dy) - 
\int_\mathbb{R} \nu_1(A_y) \nu_2(dy)\right| \tag{1} \\
\leq & d_{TV}(\mu_2, \nu_2) + d_{TV}(\mu_1, \nu_1).
\end{align}
In above expressions, $A_x = \{y: (x, y) \in A\}$ and $A_y = \{x: (x, y) \in A\}$ are section sets of $A$ for fixed $x$ and $y$. In $(1)$ we used Fubini's (or Tonelli's) theorem.
It then follows that $d_{TV}(\mu_1 \times \mu_2, \nu_1 \times \nu_2) \leq d_{TV}(\mu_1, \nu_1) + d_{TV}(\mu_2, \nu_2)$.
A: For each $i\in\{1,\dots,n\}$ we consider the maximal coupling of the random variables $X_i$ and $Y_i$ (for the reference see Section 2.5 in Frank den Hollander, "Probability Theory: The Coupling Method", be advised that the total variation distance in this reference has additional factor $2$); in this way we have random variables $X_i'$ and $Y_i'$ which are defined on the same probability space $\Omega_i$, such that $X_i \overset{d}{=} X_i'$, and $Y_i \overset{d}{=} Y_i'$, and $d_{TV}(X_i,Y_i)= \mathbb{P}( X_i' \neq Y_i' )$.
The random variables $X_1',\dots,X_n',Y_1',\dots,Y_n'$ can be considered now as random variables on the product probability space $\Omega_1\times \cdots \times \Omega_n$. In this way $X_1',\dots,X_n'$ are independent and thus the random vector
$X'=(X_1',\dots,X_n')$ filfills $X \overset{d}{=} X'$; analogously $Y\overset{d}{=} Y'$. To summarize: $X'$ and $Y'$ is a coupling of the random vectors $X$ and $Y$.
The coupling inequality implies that
$$ d_{TV}(X,Y) \leq \mathbb{P}(X' \neq Y').$$
The probability on the right-hand side can be treated in two ways.
The first approach is to use the union bound; it follows that
\begin{align*} d_{TV}(X,Y) &\leq  \mathbb{P}(X' \neq Y') \\ & = \mathbb{P}( X_1' \neq Y_1' \text{ or } \dots \text{ or } X_n'\neq Y_n') \\ & \leq  \sum_i \mathbb{P}(X_i'\neq Y_i') \\ & = \sum_i d_{TV}(X_i,Y_i) 
\end{align*}
which answers the original question.
The second approach is to calculate this probability exactly; we use the independence of the coordinates and get a better estimate
\begin{align*} d_{TV}(X,Y) & \leq 1- \mathbb{P}(X'=Y') \\ & = 1- \prod_i \mathbb{P}(X'_i=Y'_i) \\   & =  1  -  \prod_i [1-\mathbb{P}(X'_i \neq Y'_i)] \\ & =
1  -  \prod_i \left[1-  d_{TV}(X_i,Y_i) \right]
.
\end{align*}
A: This is a variation on @zhanxiong's answer. Let $Z^i= (Y_1,\dots,Y_i,X_{i+1},\dots,X_n)$. In this way $Z^0=X$ and $Z^n=Y$;
the neighboring random vectors $Z^{i-1}$ and $Z^{i}$ differ only on $i$-th coordinate.
By the triangle inequality
$$ d_{TV}(X,Y) \leq \sum_{1\leq i \leq n} d_{TV}(Z^{i-1},Z^{i}). $$
In the following we will show that the total variation distance between the neighboring random vectors
$$ d_{TV}(Z^{i-1},Z^{i}) = d_{TV}(X_{i},Y_{i}) $$
is equal to the total variation distance of the coordinate on which they differ.
By the symmetry of the problem we may assume that $i=1$.
By merging the coordinates $2,\dots,n$ into a single vector
$\mathbf{X_2}=(X_2,\dots,X_n)$ we see that it is enough to consider the case $n=2$. In other words, we need to show that
$$ d_{TV}\big( (X_1,X_2), (Y_1,X_2) \big) = d_{TV} (X_1,Y_1). $$
We proceed as in @zhanxiong's answer:
\begin{align}
& |(\mu_1 \times \mu_2)(A) - (\nu_1 \times \mu_2)(A) | \\
\leq &  \left|\int_\mathbb{R} \mu_1(A_y) \mu_2(dy) - 
\int_\mathbb{R} \nu_1(A_y) \mu_2(dy)\right| \\
\leq &  d_{TV}(\mu_1, \nu_1).
\end{align}
Above  $A_y = \{x: (x, y) \in A\}$ denotes the section set of $A$ for $y$.
This shows that
$$ d_{TV}\big( (X_1,X_2), (Y_1,X_2) \big) \leq d_{TV} (X_1,Y_1). $$
On the other hand, for the product set $A= A' \times \mathbb{R}$ we have
$$ \mathbb{P}\big\{ (X_1,X_2) \in A' \big\} - \mathbb{P}\big\{ (Y_1,X_2) \in A' \big\}= \mathbb{P}\big\{ X_1 \in A \big\} - \mathbb{P}\big\{ Y_1 \in A \big\};  $$
it follows therefore that
$$ d_{TV}\big( (X_1,X_2), (Y_1,X_2) \big) \geq d_{TV} (X_1,Y_1). $$
