2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ I was wondering why you interpret the triangle inequality that way? can you translate it to the general statement $||x+y|| \le ||x|| + ||y||$ ? $\endgroup$ – dimebucker Jul 13 '15 at 14:02
  • 3
    $\begingroup$ @dimebucker91 For distance $d$ the triangle inequality is $d(p, r)\le d(p,q)+d(q,r)$. Here we have the opposite... $\endgroup$ – d.k.o. Jul 13 '15 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.