Toolbox

T1: Total Variation Distance

Reminder: This post contains 749 words · 3 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=supA⊂E∣μ(A)−ν(A)∣\lVert \mu - \nu \rVert_{\text{tvd}}= \textup{sup}_{A \subset E}\lvert \mu(A) - \nu(A) \rvert

Since ∑x∈Eμ(x)=∑x∈Eν(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) \leq \mu(x)}\nu(x) - \mu(x) ∥μ−ν∥tvd=12∑x∈E∣μ(x)−ν(x)∣\lVert \mu - \nu \rVert_{\text{tvd}} = \frac{1}{2} \sum_{x\in E} \lvert \mu(x) - \nu(x) \rvert

Let B:={x:μ(x)≥ν(x)}B: = \{x : \mu(x) \geq \nu(x) \}

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

P(X≠Y)≥P(X∈B,Y∈Bˉ)=P(X∈B)−P(X∈B,Y∈B)≥P(X∈B)−P(Y∈B)=μ(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}}