Total Variation Distance

The total variation distance between two probability measures $P$ and $Q$ on a sigma-algebra $\mathcal{F}$ of subsets of the sample space $\Omega$ is defined via

$$\mathrm{TV}(P,Q)=\underset{A\in \mathcal{F}}{\sup }\left|P(A)-Q(A)\right|$$

Informally, this is the largest possible difference between the probabilities that the two probability distributions can assign to the same event.

One direct implication from the definition is that if two distributions have disjoint support, i.e., $\nu (\mathrm{supp}(P)\cap \mathrm{supp}(Q))=0$, where $m$ is the measure on the sigma field, then their TV distance is 1. For example, the TV distance between a discrete and a continuous distribution is 1, because on the common sample space, the support of the discrete distribution has measure 0.

Rmk

TV distance does not tensorize:

$$\mathrm{TV}(P_1\otimes P_2,Q_1\otimes Q_2)/\lesssim \mathrm{TV}(P_1,Q_1)+\mathrm{TV}(P_2,Q_2).$$

In other words, a property in one dimension does not hold in multiple dimensions. Specifically, suppose we have $n$ iid samples from $P_{{\theta }_1}$. We do not have relationship

$$\mathrm{TV}(P_{{\theta }_1}^n,P_{{\theta }_2}^n)\le n\mathrm{TV}(P_{{\theta }_1},P_{{\theta }_2}).$$

Therefore, in practice, it’s usually more convenient to calculate other distances that tensorize, such as the KL Divergence, Wasserstein Distance, and Hellinger Distance.

L1 Norm

Thm

The TV distance is equivalent to the L1 norm.

$$\mathrm{TV}(p,q)=\frac{1}{2}\Vert p-q{\Vert }_1.$$

First Proof

Let $B=\{p\ge q\}$. Note that

$$\begin{array}{rl}{\int }_{\Omega }\left|p-q\right|d\nu & ={\int }_B(p-q)d\nu +{\int }_{\Omega \setminus B}(q-p)d\nu \\ & \le 2\underset{A}{\sup }\left|{\int }_A(p-q)d\nu \right|\\ & =2\mathrm{TV}(p,q).\end{array}$$

On the other side, note first that

$${\int }_{\Omega }(p-q)d\nu =P(\Omega )-Q(\Omega )=0$$

and hence

$${\int }_B(p-q)d\nu ={\int }_{\Omega \setminus B}(q-p)d\nu$$

Now for any $A\in \mathcal{F}$, we have

$$\begin{array}{rl}\left|{\int }_A(p-q)d\nu \right|& =\max \left\{{\int }_A(p-q)d\nu ,{\int }_A(q-p)d\nu \right\}\\ & \le \max \left\{{\int }_{A\cap B}(p-q)d\nu ,{\int }_{A\cap (\Omega \setminus B)}(q-p)d\nu \right\}\\ & \le \max \left\{{\int }_B(p-q)d\nu ,{\int }_{\Omega \setminus B}(q-p)d\nu \right\}\\ & ={\int }_B(p-q)d\nu \\ & =\frac{1}{2}{\int }_{\Omega }\left|p-q\right|d\nu \end{array}$$

Taking the supremum over $A\in \mathcal{F}$, gives

$$\underset{A}{\sup }\left|{\int }_A(p-q)d\nu \right|\le \frac{1}{2}{\int }_{\Omega }\left|p-q\right|d\nu$$

which is the other needed inequality.

Second Proof

Again, let $B=\{p\ge q\}$. We know that ${\int }_B(p-q)\mathrm{d}\nu =\frac{1}{2}{\int }_{\Omega }|p-q|\mathrm{d}\nu$. Therefore, we only need to show ${\sup }_A\left|{\int }_A(p-q)\mathrm{d}\nu \right|=\left|{\int }_B(p-q)\mathrm{d}\nu \right|=\left|{\int }_{B^C}(p-q)\mathrm{d}\nu \right|={\int }_B(p-q)\mathrm{d}\nu$, where the last two equalities are known.

For any $A\notin \{B,B^C\}$, we suppose $P(A)\ge Q(A)$ WLOG. Then,

$$(P(B)-Q(B))-(P(A)-Q(A))=\underset{\ge 0}{\underbrace{{\int }_{B\setminus A}(p-q)\mathrm{d}\nu }}-\underset{\le 0}{\underbrace{{\int }_{A\setminus B}(p-q)\mathrm{d}\nu }}>0,$$

where the strict inequality is because two equalties cannot hold at the same time, as $A\notin \{B,B^C\}$. Then,

$$(P(B)-Q(B))-(P(A)-Q(A))=\left|{\int }_B(p-q)\mathrm{d}\nu \right|-\left|{\int }_A(p-q)\mathrm{d}\nu \right|>0,$$

which further implies

$$A\notin \arg \underset{A}{\sup }\left|{\int }_A(p-q)\mathrm{d}\nu \right|.$$

Thus, $B$ and $B^C$ are the sets that achieve the supremum.

Optimal Transport Interpretation

TV can be interpreted as the distance from transforming one distribution to another in an optimal transport perspective.

Formally, suppose $\mathrm{TV}(P_1,P_2)=\gamma$. Then, there exists a joint distribution of $(X_1,X_2)\sim P$ such that the marginal distributions are $P_1$ and $P_2$, and $P(X_1=X_2)=1-\gamma$.

This means that we can transform $P_1$ to $P_2$ by moving $\gamma$ mass from $P_1$ to $P_2$, and the remaining mass remains unchanged.

Proof

Suppose $P_1,P_2$ have PDF/PMF $f_1,f_2$. Then note that

$$\begin{array}{rl}{\int }_{\mathcal{X}}{f}_1\wedge f_2=& {\int }_{\{f_1\le f_2\}}{f}_1+{\int }_{\{f_2<f_1\}}{f}_2\\ =& 1-{\int }_{\{f_1\le f_2{\}}^c}{f}_1+1-{\int }_{\{f_2<f_1{\}}^c}{f}_2\\ =& 2-{\int }_{\{f_1>f_2\}}(f_1-f_2)-{\int }_{\{f_2\ge f_1\}}(f_2-f_1)\\ & -{\int }_{\{f_1>f_2\}}{f}_2-{\int }_{\{f_2\ge f_1\}}{f}_1\\ =& 2-2\Vert P_1-P_2{\Vert }_{\mathrm{TV}}-{\int }_{\mathcal{X}}{f}_1\wedge f_2,\end{array}$$

which implies

$${\int }_x{f}_1\wedge f_2=1-\Vert P_1-P_2{\Vert }_{\mathrm{TV}}=1-\gamma$$

Now note that due to the marginal constraint,

$$P(X_1=X_2=x)\le P(X_1=x)\wedge P(X_2=x),$$

which implies

$$\underset{P}{\sup }P(X_1=X_2)\le {\int }_x{f}_1\wedge f_2=1-\gamma$$

OTOH, we can define

$$P(X_1=x,X_2=x)=P(X_1=x)\wedge P(X_2=x)\Rightarrow P(X_1=X_2)=1-\gamma$$

Then we can specify the other values of $P$ to make it meet the marginal constraint.

!todo See also Hw 3.4.

Sample Gain

It’s intuitive that more iid samples help distinguish two distributions. Formally, we claim

$$\mathrm{TV}(P_0,P_1)\le \mathrm{TV}(P_0\times P_0,P_1\times P_1)$$

First Proof

The first proof is for continuous distributions. Let $B=\{f_0>f_1\}$ and WLOG, ${\int }_B{f}_0+{\int }_B{f}_1\ge 1$. Note that $B\times B\subset B^{\mathrm{opt}}=\{f_0\times f_0>f_1\times f_1\}$. Thus,

$$\begin{array}{rl}\mathrm{TV}(P_0\times P_0,P_1\times P_1)& \ge {\int }_{B\times B}(f_0\times f_0-f_1\times f_1)\mathrm{d}x\mathrm{d}y\\ & ={\int }_{B\times B}(f_0+f_1)\mathrm{d}x(f_0-f_1)\mathrm{d}y\\ & =\mathrm{TV}(P_0,P_1){\int }_B(f_0+f_1)\mathrm{d}x\\ & \ge \mathrm{TV}(P_0,P_1).\end{array}$$

Second Proof

The second proof applies to general distributions. By the set relationship, we have

$$\begin{array}{rl}\mathrm{TV}(P_0,P_1)& =\underset{B}{\sup }\left|P_0(B)-P_1(B)\right|\\ & =\underset{B}{\sup }\left|P_0(B)\times P_0(\mathcal{X})-P_1(B)\times P_1(\mathcal{X})\right|\\ & =\underset{C=B\times \mathcal{X}}{\sup }\left|P_0\times P_0(C)-P_1\times P_1(C)\right|\\ & \le \underset{C}{\sup }\left|P_0\times P_0(C)-P_1\times P_1(C)\right|\\ & =\mathrm{TV}(P_0\times P_0,P_1\times P_1).\end{array}$$