T1: Total Variation Distance

October 09, 2024

• Definition
• Useful Tips

Total variation distance is very useful in many areas. This post shows some useful properties.

Definition

Consider two distributions $\mu, \nu$ (probabilities on $E$), the total variation distance between $\mu$ and $\nu$ is as follows.

$$\lVert \mu - \nu \rVert_{\text{tvd}}= \textup{sup}_{A \subset E}\lvert \mu(A) - \nu(A) \rvert$$

Since $\sum_{x\in E} \mu(x) = \sum_{x\in E} \nu(x) = 1$, then we have

$$\sum_{\mu(x) \geq \nu(x)}\mu(x) - \nu(x) = \sum_{\nu(x) \geq \mu(x)}\nu(x) - \mu(x)$$ $$\lVert \mu - \nu \rVert_{\text{tvd}} = \frac{1}{2} \sum_{x\in E} \lvert \mu(x) - \nu(x) \rvert = \frac{1}{2} \lvert \lvert \mu(x) - \nu(v) \rvert\rvert_1$$

Let $B: = \{x : \mu(x) \geq \nu(x) \}$

Let $X\sim \mu, Y \sim \nu$.

$$\mathbb{P}(X \neq Y ) \geq P(X\in B, Y \in \bar B) = \\ \mathbb{P}(X\in B) - \mathbb{P}(X\in B, Y\in B) \geq \\ \mathbb{P}(X\in B) - \mathbb{P}(Y\in B) = \mu(B) - \nu(B) = \lVert \mu - \nu \rVert_{\text{tvd}}$$

Useful Tips

By the definition $\lVert \mu - \nu \rVert_{\text{tvd}}= \textup{sup}_{A \subset E}\lvert \mu(A) - \nu(A) \rvert$

We consider the all possible $A$. When we need to estimate a lower bound, we can select $A$ satisfying some properties.

For example, we define

A:={transcripts where f(transcript)=1}

Then,

$Pr[\pi(0,0)\in A]=Pr[output=1\mid (0,0)]$ and $Pr[\pi(1,1)\in A]=Pr[output=1\mid (1,1)]$

Then $\textup{sup}_{A \subset E}\lvert \pi(0,0) - \pi(1,1) \rvert \\ \geq \lvert Pr[\pi(0,0)\in A] - Pr[\pi(1,1)\in A]\rvert \\ \geq Pr[output=1\mid (0,0)] - Pr[output=1\mid (1,1)]$