Toolbox

T1: Total Variation Distance

Reminder: This post contains 1322 words · 4 min read · by Xianbin

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

Definition

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

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

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

μ(x)ν(x)μ(x)ν(x)=ν(x)μ(x)ν(x)μ(x)\sum_{\mu(x) \geq \nu(x)}\mu(x) - \nu(x) = \sum_{\nu(x) \geq \mu(x)}\nu(x) - \mu(x) μνtvd=12xEμ(x)ν(x)=12μ(x)ν(v)1\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:μ(x)ν(x)}B: = \{x : \mu(x) \geq \nu(x) \}

Let Xμ,YνX\sim \mu, Y \sim \nu.

P(XY)P(XB,YBˉ)=P(XB)P(XB,YB)P(XB)P(YB)=μ(B)ν(B)=μνtvd\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 μνtvd=supAEμ(A)ν(A)\lVert \mu - \nu \rVert_{\text{tvd}}= \textup{sup}_{A \subset E}\lvert \mu(A) - \nu(A) \rvert

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

For example, we define

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

Then,

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

Then supAEπ(0,0)π(1,1)Pr[π(0,0)A]Pr[π(1,1)A]Pr[output=1(0,0)]Pr[output=1(1,1)]\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)]