relative entropy

Let $p$ and $q$ be probability distributions with supports $𝒳$ and $𝒴$ respectively, where $𝒳\subset 𝒴$. The relative entropy or Kullback-Leibler distance between two probability distributions $p$ and $q$ is defined as

$$D(p||q):=\sum _{x\in 𝒳}p(x)\log \frac{p(x)}{q(x)}.$$ (1)

While $D(p||q)$ is often called a distance, it is not a true metric because it is not symmetric and does not satisfy the triangle inequality. However, we do have $D(p||q)\ge 0$ with equality iff $p=q$.

$-D(p||q)$ $=-{\displaystyle \sum _{x\in 𝒳}}p(x)\log {\displaystyle \frac{p(x)}{q(x)}}$ (2)

$={\displaystyle \sum _{x\in 𝒳}}p(x)\log {\displaystyle \frac{q(x)}{p(x)}}$ (3)

$\le \log \left({\displaystyle \sum _{x\in 𝒳}}p(x){\displaystyle \frac{q(x)}{p(x)}}\right)$ (4)

$=\log \left({\displaystyle \sum _{x\in 𝒳}}q(x)\right)$ (5)

$\le \log \left({\displaystyle \sum _{x\in 𝒴}}q(x)\right)$ (6)

$=0$ (7)

where the first inequality follows from the concavity of $\log (x)$ and the second from expanding the sum over the support of $q$ rather than $p$.

Relative entropy also comes in a continuous version which looks just as one might expect. For continuous distributions $f$ and $g$, $𝒮$ the support of $f$, we have

$$D(f||g):={\int }_{𝒮}f\log \frac{f}{g}.$$ (8)

Title	relative entropy
Canonical name	RelativeEntropy
Date of creation	2013-03-22 12:19:32
Last modified on	2013-03-22 12:19:32
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	10
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 60E05
Classification	msc 94A17
Synonym	Kullback-Leibler distance
Related topic	Metric
Related topic	ConditionalEntropy
Related topic	MutualInformation
Related topic	ProofOfGaussianMaximizesEntropyForGivenCovariance