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 μ,ν (probabilities on E), the total variation distance between μ and ν is as follows.
∥μ−ν∥tvd=supA⊂E∣μ(A)−ν(A)∣
Since ∑x∈Eμ(x)=∑x∈Eν(x)=1, then we have
μ(x)≥ν(x)∑μ(x)−ν(x)=ν(x)≥μ(x)∑ν(x)−μ(x)
∥μ−ν∥tvd=21x∈E∑∣μ(x)−ν(x)∣=21∣∣μ(x)−ν(v)∣∣1
Let B:={x:μ(x)≥ν(x)}
Let X∼μ,Y∼ν.
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
Useful Tips
By the definition ∥μ−ν∥tvd=supA⊂E∣μ(A)−ν(A)∣
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[π(0,0)∈A]=Pr[output=1∣(0,0)]
and
Pr[π(1,1)∈A]=Pr[output=1∣(1,1)]
Then
supA⊂E∣π(0,0)−π(1,1)∣≥∣Pr[π(0,0)∈A]−Pr[π(1,1)∈A]∣≥Pr[output=1∣(0,0)]−Pr[output=1∣(1,1)]