Comparing the Kullback-Leibler divergence to the total variation distance on discrete probability densities.

Question

I am trying to get a clearer understanding on how the Kullback_Leibler divergence ranks distributions with respect to the total variation in the discrete setting.

let $P,Q$ be two probability measures on $(\Omega, \mathscr {F})$, and let $\nu$ be a $\sigma$-finite measure on the same event space such that $P \ll v, Q \ll v$. Define $\frac{dP}{dv}=p$, $\frac{dQ}{dv}=q$.

The total variation distance between P and Q is then:

$$ V(P,Q) = \frac{1}{2} \int |p-q|d\nu $$

(in the discrete case we replace the integral with a summation). It is very obvious geometrically what the total variation is measuring since it's fundamentally the $L^1$ distance and no "special treatment" is given for different values of $p(x)$ or $q(x)$.

The Kullback-Leibler divergence is defined as:

$$KL(P,Q) = -\int p \log{\frac{q}{p}} d\nu$$

I understand the information theoretic nature of this divergence (and know it is not symmetric or that the triangle inequality does not hold). What I am missing is how actually does this divergence rate distributions against one another.

To get my point across I give an example, say I have three probability distributions $P_1,P_2,P_3$ s.t.

• $P_1( X = 0) = 1/4 , P_1( X = 1) = 1/2, P_1( X = 2) = 1/4 $ blue.
• $P_2( X = 0) = 1/3 , P_2( X = 1) = 1/3, P_2( X = 2) = 1/3 $ green.
• $P_3( X = 0) = 1/4 , P_3( X = 1) = 1/3, P_3( X = 2) = 5/12 $ light blue.

The total variation distance between $P_1$ and $P_2$ is the same as the one between $P_1$ and $P_3$ this is geometrically intuitive since the sum of distances between the top of the charts in the two cases is the same.

I would like to find a similar way to inspect the chart to quickly determine what should be the rankings for the Kullback-Leibler divergence. For example $KL(P_1,P_2) \approx 0,06$ and $KL(P_1,P_3) \approx 0,07$ but what is the explanation behind this ranking.

Moreover when a discrete density assigns probability zero to a value the K-L divergence can completely miss the difference in the distributions since the convention is this case is that $x \log \frac{y}{x}|_{x = 0}= 0$. To cut it short I can't find a (geometric) way to compare the K-L divergence to a symmetric distance like the total variation and I am having some doubts on the validity of considering the K-L divergence a good measure of distance between distributions.

Answer 1

[Too long for a comment, but will restore your faith in KL divergence].

Here's why I like KL-divergence. Let's say you have two probability measures $\mu$ and $\nu$ on some finite set $X$. Someone secretly chooses either $\mu$ or $\nu$. You receive a certain number $T$ of elements of $X$ chosen randomly and independently according to the secret measure. You want to guess the secret measure correctly with high probability. What do you do?

The best "algorithm" to follow would be to observe the $T$ samples $x_1,\dots,x_T$ and choose $\mu$ or $\nu$ based on which one is more likely to generate these $T$ samples. The probability that $\mu$ generates these samples is $\prod_{j=1}^T \mu(x_j)$, and the probability $\nu$ generates these samples is $\prod_{j=1}^T \nu(x_j)$. So, we choose $\mu$ iff $\prod_{j=1}^T \frac{\mu(x_j)}{\nu(x_j)} > 1$, which is the same as $\sum_{j=1}^T \log \frac{\mu(x_j)}{\nu(x_j)} > 0$. If we let $Z : X \to [0,\infty]$ be the random variable defined by $Z(x) = \log \frac{\mu(x)}{\nu(x)}$, then the expected value of $Z$ under $\mu$ is exactly the KL-divergence between $\mu$ and $\nu$. And then of course the sum of $T$ independent copies of $Z$ has expectation $T\cdot KL(\mu,\nu)$.

As $T$ increases, by the weak law of large numbers, the average $\frac{1}{T}\sum_{t \le T} Z_t$ converges in probability to $KL(\mu,\nu)$. The fact that $KL(\mu,\nu) > 0$ (if $\mu \not = \nu$) corresponds to the fact that our algorithm will succeed with probability tending to $1$ as $T \to \infty$.

The point is that KL-divergence is an important quantity when trying to distinguish between different distributions, based on observed samples.