4
$\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 counterexamples for symmetry, but I was wondering if anyone has any simple counterexamples to show that it does not satisfy the triangle inequality.

$\endgroup$

1 Answer 1

7
$\begingroup$

Take $\Omega=\{0,1\}$; $p(0)=1/2$, $q(0)=1/4$, $r(0)=1/10$:

$$ H(p\mid q)+H(q\mid r)\approx 0.24<H(p\mid r)\approx 0.51 $$

($\log$ with base $e$).

$\endgroup$
2
  • 1
    $\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$ Commented Jul 13, 2015 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$
    – user140541
    Commented Jul 13, 2015 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .