I've recently begun to study the basics of Information Theory using this pdf: https://web.stanford.edu/~montanar/RESEARCH/BOOK/partA.pdf, and have just read about Kullback-Leiber Divergence; there Gibbs' inequality is proven (although it isn't called by that name) using the convexity of the function: $-\log_2 x$ and Jensen's Inequality; some other proofs use the same idea with other convex functions like $\ x\log_2 x$ .

All well so far except for one thing: The functions that are used in the proofs are not $-\log_2 x$ or $\ x\log_2 x$ , but their composition with other functions like: $-\log_2 \left(\frac{q(x)}{p(x)}\right)$ or $\ \left(\frac{q(x)}{p(x)}\right)\log_2 \left(\frac{q(x)}{p(x)}\right)$ with $q(x)$ and $p(x)$ being probability distributions with $x \in \mathcal I$ such that $\ \forall x \in \mathcal I, \ q(x),p(x) \neq 0$ and $\sum \limits_{x \in \mathcal I} q(x) = 1$ and $\sum \limits_{x \in \mathcal I} p(x) = 1$.

The thing is: How do i know if the new composite functions are convex and so Jensen's Inequality applies? depending on $q(x)$ and $p(x)$, $f(x)=q(x)/p(x)$ may or may not be convex, and may or may not be non-decreasing; and i know examples of compositions of convex functions that are not convex.

I understood another proof that didn't use Jensen's Inequality at all, it's this kind of proofs that i have trouble with.

All help would be appreciated, regarding the question and also regarding style (i'm new so...)

Thank you all.

  • Jensen says that for convex $f$ and random variable $Y$, $\mathbb{E}f(Y)\ge f(\mathbb{E}Y)$
  • $f(x)=-\log x$ is convex
  • We can let $Y=\frac{p(X)}{q(X)}$. As $X$ is a random variable, $Y$ is also just a random variable.
  • Jensen thus says that $\mathbb{E}[-\log Y] \ge -\log\mathbb{E}Y$
  • Taking expectations with respect to $q$, this becomes

$$\mathbb{E}\left[-\log \frac{p(X)}{q(X)}\right]=\mathbb{E}\left[\log \frac{q(X)}{p(X)}\right]=D_{KL}(q||p) \ge -\log\mathbb{E}_q\left(\frac{p(X)}{q(X)}\right)=-\log\mathbb{E}_p(1)=0$$

and thus, Gibbs' inequality is proven.

  • $\begingroup$ $Y$ can be any function? Isn't there a problem if the composite function: $f \circ Y (x)$ isn't convex? $\endgroup$ – IDUTDP Dec 20 '16 at 20:56
  • $\begingroup$ have edited answer to address this - $Y$ is just a random variable $\endgroup$ – πr8 Dec 20 '16 at 20:58
  • $\begingroup$ Well a random variable is a function =P. It seems my problem comes from a misunderstanding of Jensen's Inequality, i'll have to review the topic. Thank you for your answer :) $\endgroup$ – IDUTDP Dec 20 '16 at 20:58
  • $\begingroup$ you're correct! though in the context of jensen, you typically have one "variable" ($Y$) and one "function" ($f$), so i thought that might be unhelpful/confounding in trying to explain the solution. $\endgroup$ – πr8 Dec 20 '16 at 21:00

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.