1
$\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$
1

1 Answer 1

3
$\begingroup$

There are several mistake in what you have done. It is by no means to true that density functions $g$ satisfy the inequalities $0 \leq g(x) \leq 1$. For example $2I_{(0,\frac1 2 )}$ is a density function. Secondly I don't know how you finish the proof because you have ended up with a negative number plus a positive number and there is no reason why the sum is positive.

Here is a proof: $E_F(\log \frac {f(X)} {g(X)}) =-E_F(-\log \frac {f(X)} {g(X)})=-E_F \log \frac {g(X)} {f(X)}=E_F (-\log \frac {g(X)} {f(X)}) \geq -\log ( E_F \frac {g(X)} {f(X)})$ by Jensen's Inequality. Now $E_F (\frac {g(X)} {f(X)})=\int \frac {g(x)} {f(x)} f(x)dx=\int g(x)dx=1$ and $\log 1=0$.

$\endgroup$
2
  • $\begingroup$ What is the function $2I_{(0,1/2)}$ exactly? $\endgroup$ Commented Jun 3, 2020 at 9:24
  • $\begingroup$ It is the function which has the value $2$ for points in $(0,1/2)$ and $0$ for all other points. @stochasticmrfox $\endgroup$ Commented Jun 3, 2020 at 9:25

You must log in to answer this question.

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