7
$\begingroup$

I wish to prove that relative entropy(Kullback-Liebler divergence) is always non-negative. I.e. that $$I^{KL}(F;G)=E_F\left[\log\frac{f(X)}{g(X)}\right]\geq0$$ where F,G are two different probability distributions.

(there is a much shorter proof for the case where F,G are continuous but I'm curious to see the following version is correct because it would capture both the continuous and discrete case)

The proof will make use of :

1.Jensen's inequality: $$E(h(X))\geq h(E(X))$$ for a convex function h(x).

2.The fact that entropy $E_F[\log f(X)]$ is always positive.

Proof:

$I^{KL}(F;G)=E_F\left[\log\frac{f(X)}{g(X)}\right]$ $=E_F[\log f(X)]-E_F[\log (g(X)]$

log(x) is concave, therefore h(x)=-\log(x) is convex as required.

$-E_F[\log (g(X)]=E_F[-\log (g(X)]$ (by linearity of expectation)

$E_F[-\log (g(X)]\geq -\log E_F[g(X)]$ by Jensen's inequality.

Now: g is a probability density(or mass) function for the random variable X, thus $0\leq g(x)\leq 1$ for all possible values x of X. $\implies 0\leq g(X)\leq 1$

$\implies 0\leq E(g(X)) \leq 1 $

$\implies \log[E(g(X))] \leq 0$

$\implies -\log[E(g(X))] \geq 0$

$\implies E_F[-\log (g(X)]\geq -\log[E(g(X))] \geq 0$

Therefore $-E_F[\log (g(X)]\geq 0$ and thus $I^{KL}(F;G) \geq 0$

$\endgroup$
4
  • 2
    $\begingroup$ It is not the case that $g$ must be bounded above by $1.$ For a counterexample, consider any Normal distribution with a standard deviation less than $1/\sqrt{2\pi}.$ Indeed, in the case of a distribution that is not absolutely continuous but not discrete, what would $g$ even be?? $\endgroup$
    – whuber
    Jun 2 '20 at 23:37
  • $\begingroup$ Crossposted at math.stackexchange.com/q/3703014/321264. $\endgroup$ Jun 3 '20 at 5:21
  • $\begingroup$ This is also Gibb's inequality and you can use $$\log(f(x)/g(x)) = -\log(g(x)/f(x)) \geq 1- g(x)/f(x)$$ to write without Jensen's inequality. $$\int \log(f(x)/g(x)) f(x) dx \geq \int (1 - g(x)/f(x)) f(x) dx = \int f(x) -g(x) dx =0$$ $\endgroup$ Jun 3 '20 at 12:54
  • 2
    $\begingroup$ Linking to Whuber's answer. You do not only have that $g(x)$ is not bounded by 0 and 1 for densities (but it can also be larger than 1), you also have that the entropy can be negative/positive for density functions. This occurs for instance clearly for any density that has $f(x) <1$ for all $x$ versus $f(x) > 1$ for all $x$. In the case of discrete functions than you have always positive entropy, but note that this means negative $E[log(f(X)]$ while you argued that this is positive. $\endgroup$ Jun 3 '20 at 13:14
8
$\begingroup$

I think you have introduced good ideas, but some care is needed to make sense of all this.

The unifying concept is of absolutely continuous measure. Given two measures $\nu$ and $\mu$ on the same measure space, $\nu$ is said to be absolutely continuous with respect to $\mu$ provided $\nu$ never assigns a nonzero value to any set of zero $\mu$ measure. The Radon-Nikodym Theorem asserts this is tantamount to the existence of a $\mu$-measurable function $f$ which converts $\mu$ into $\nu;$ that is, for all measurable sets $A,$

$$\nu(A) = \int f\,\mathrm{d}\mu.$$

In this case $f$ is the Radon-Nikodym derivative of $\nu$ with respect to $\mu,$ written

$$f = \frac{\mathrm{d}\nu}{\mathrm{d}\mu}.$$

(Think of $f$ as a "multiplicative change of measure:" by multiplying the values of $\mu$ it distorts $\mu$ into a different measure, which is precisely $\nu;$ and provided almost all values of $f$ are finite, $f$ cannot distort the measure too much and make it "singular.")

The two most prominent examples in statistics are

  1. $\mu$ is Lebesgue measure on $\mathbb{R}^n$ and $\nu$ is the probability measure of an absolutely continuous random variable $X$ with values in $\mathbb{R}^n.$ In this case $f$ is the probability density function (pdf) of $X.$

  2. $\mu$ is the counting measure on $\mathbb{R}^n$ and $\nu$ is the probability measure of a discrete variable $X$ with values in $\mathbb{R}^n.$ In this case $f$ is the probability mass function (pmf) of $X.$

Measure is the unifying concept and the Radon-Nikodym derivative simultaneously handles ratios of pmfs and ratios of pdfs.

The setting of the question concerns two random variables $X$ and $Y$ absolutely continuous with respect to some measure $\mu,$ with Radon-Nikodym derivatives $f$ and $g$ respectively. Suppose, further, that $Y$ is absolutely continuous with respect to $X,$ the probability measure of $Y$ is $\lambda,$ and the probability measure of $X$ is $\nu.$ It follows easily (from the definitions) that the function $h = g/f$ is the Radon-Nikodym derivative of $\lambda$ with respect to $\nu$ and it is almost everywhere defined with respect to the measure $\mu.$

In any event, because $\log$ is a convex extended-real function on the non-negative reals (taking the value $-\infty$ at $0$), its value at any weighted average of a set of points is never less than the weighted average of its values at those points (Jensen's Inequality). The broadest concept of "weighted average" is the integral against a measure like $\nu;$ thus, for any $\nu$-measurable function $h:\mathbb{R}\to [0,\infty),$

$$\log \int h\, \mathrm{d}\nu \ge \int \log(h)\,\mathrm{d}\nu.$$

(When both sides are exponentiated this is also known as the (weighted) Arithmetic Mean - Geometric Mean Inequality.)

Plugging in $h = g/f$ and $f = \mathrm{d}\nu/\mathrm{d}\mu$ and remembering all probability measures integrate to unity (as part of their definition) gives

$$\eqalign{ 0 &= \log(1) = \log \int \mathrm{d}\lambda &&\color{Gray}{\lambda\text{ is a probability measure}}\\ &= \log \int g\,\mathrm{d}\mu &&\color{Gray}{g = \frac{\mathrm{d}\lambda}{\mathrm{d}\mu}}\\ &= \log \int \frac{g}{f}\,f\,\mathrm{d}\mu &&\color{Gray}{gf/f=g}\\ &= \log \int h \,\mathrm{d}\nu &&\color{Gray}{h = g/f\text{ and }f = \frac{\mathrm{d}\nu}{\mathrm{d}\mu}} \\ &\ge \int \log(h)\,\mathrm{d}\nu &&\color{Gray}{\text{Jensen}} \\ &= \int \log\left(\frac{g}{f}\right)\,f\,\mathrm{d}\mu &&\color{Gray}{h=g/f\text{ and } f = \frac{\mathrm{d}\nu}{\mathrm{d}\mu}}. }$$

Negating this inequality produces the desired result, QED.

$\endgroup$
2
  • $\begingroup$ I'm not all to familiar with modern probability theory(measures etc). What's a good introductory resource? $\endgroup$ Jun 3 '20 at 9:18
  • 1
    $\begingroup$ You really don't need to know much beyond the basic definitions. One very gentle, yet reasonably rigorous, introduction is the first (slim) volume in Steven Shreve's two-part treatise on Stochastic Calculus in Finance, followed by the first few chapters in the second volume (for the general setting). $\endgroup$
    – whuber
    Jun 3 '20 at 12:11

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.