# Kullback - Leibler Divergence and 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 counter examples for symmetry, but I was wondering if anyone has any simple counter examples to show that it does not satisfy the triangle inequality.

## 1 Answer

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