# Is there a counterexample that shows that the KL divergence does not satisfy the triangle inequality?

The KL Divergence, or relative entropy for two probability distributions $$p,q$$ on $$\Omega$$ is defined as:

$$H(p|q) = \int_{\Omega} p(\omega) \log \frac{p(\omega)}{q(\omega)} d\omega$$

This is a divergence and not a distance since it does not satisfy symmetry nor does it satisfy the triangle inequality. I have seen counterexamples for symmetry, but I was wondering if anyone has any simple counterexamples to show that it does not satisfy the triangle inequality.

Take $\Omega=\{0,1\}$; $p(0)=1/2$, $q(0)=1/4$, $r(0)=1/10$:
$$H(p|q)+H(q|r)\approx 0.24<H(p|r)\approx 0.51$$
($\log$ with base $e$).
• I was wondering why you interpret the triangle inequality that way? can you translate it to the general statement $||x+y|| \le ||x|| + ||y||$ ? – dimebucker Jul 13 '15 at 14:02
• @dimebucker91 For distance $d$ the triangle inequality is $d(p, r)\le d(p,q)+d(q,r)$. Here we have the opposite... – d.k.o. Jul 13 '15 at 18:47