Understanding Gibbs's inequality

Question

Short version

Gibbs's inequality is a simple inequality for real numbers, usually understood information-theoretically. In the jargon, it states that for two probability measures on a finite set, the relative entropy is always nonnegative.

I'd like to hear about non-information-theoretic ways of understanding it. I'd be particularly pleased if there were some nice geometric interpretation.

Statement and proof of Gibbs's inequality

For natural numbers $n$, let $\mathbf{P}_n$ denote the set of probability measures on an $n$-element set: that is, $$ \mathbf{P}_n = \{ p \in \mathbb{R}^n : p_1, \ldots, p_n \geq 0, \sum p_i = 1 \}. $$ Theorem (Gibbs) Let $p \in \mathbf{P}_n$. Then, for $q$ varying in $\mathbf{P}_n$, the quantity $\prod q_i^{p_i}$ is maximized by $q = p$.

Usually this is stated in logarithmic form: $-\sum p_i \log q_i \geq -\sum p_i \log p_i$ for all $p, q \in \mathbf{P}_n$. But I'd like to reach a direct understanding of the product form.

There are at least two extremely easy proofs. Ignoring zero probabilities, they run as follows. The first: since $\log$ is concave, $\sum p_i \log (q_i/p_i) \leq \log \sum p_i (q_i/p_i) = 0$. The second: since $\log x \leq x - 1$ for all $x$, we have $\sum p_i \log (q_i/p_i) \leq \sum p_i (q_i/p_i - 1) = 0$.

The question

Can Gibbs's inequality, in the product form stated above, be understood geometrically? Or if not geometrically, is there an intuitive interpretation other than the information-theoretic one? (I have nothing against information theory — it's just that I'd like to have multiple ways of thinking about it.)

There is a hint that Gibbs's inequality can be interpreted as some kind of isoperimetric inequality. Take $p$ to be the uniform distribution. Then the inequality states that for $q \in \mathbf{P}_n$, the quantity $(q_1 q_2 \cdots q_n)^{1/n}$ is maximized by taking $q$ to be uniform. We might as well remove the power $1/n$, and then the result is: among all $n$-dimensional boxes of prescribed total edge-length, the cube has the greatest volume.

But I see no way of extending the isoperimetric interpretation to non-uniform $p$. For example, take $p = (2/3, 1/3)$. Then Gibbs states that among all $q \in \mathbf{P}_2$, the maximum value of $q_1^2 q_2$ is attained by $q = (2/3, 1/3)$. This doesn't seem geometrically obvious to me in the way that the uniform case does.

Answer 1

The trick is to use appropriate units or scaling for the different edges of the rectangular parallelopiped when computing its volume. More specifically, apply the uniform probability argument (i.e., the isoperimetric inequality) to the probabilities $$\tilde{p}_i = \frac{1}{n}\text{ and } \tilde{q_i} = \frac{q_i}{p_i}\left(\sum \frac{q_i}{p_i}\right)^{-1}. $$

Answer 2

If you understand the case of equal weights, the general case following by a simple trick. I'll do your example of maximizing $q_1^2 q_2$ for $q_1+q_2=1$.

Set $(r_1, r_2, r_3) = (q_1/2, q_1/2, q_2)$. Then our goal is to maximize $r_1 r_2 r_3$ subject to the side constraints $r_1+r_2+r_3=1$ and $r_1=r_2$. By the equal weights case, the maximum of $r_1 r_2 r_3$ given the first constraint is achieved at $(1/3, 1/3, 1/3)$. Since $r_1 = r_2$ at this point, the second constraint does not affect the answer.

This trick lets you deduce the case of any rational weights from the equal weights case, and then the case of real weights follows by continuity.

Answer 3

Here is an alternative way of looking at the inequality.

We wish to prove that

\begin{equation*} \frac{\prod_i q_i^{p_i}}{\prod_i p_i^{p_i}} = \prod_i \left(\tfrac{q_i}{p_i}\right)^{p_i} \le 1, \end{equation*} with equality iff $q_i=p_i$.

Apply the weighted AM-GM inequality to the latter product above; this yields

\begin{equation*} \prod_i \left(\tfrac{q_i}{p_i}\right)^{p_i} \le \sum_i p_i(q_i/p_i)=1. \end{equation*}

But we know that in the weighted AM-GM inequality, equality holds iff all the $q_i/p_i$ are equal, and in the generic case this can only happen if $q_1/p_1=q_2/p_2=\cdots=q_n/p_n=1$, concluding the claim.

Answer 4

I don't have a geometric interpretation of this inequality, but I do like to think of it as a limiting case of the Holder inequality: Given $0 < \alpha < 1$,

$$ \frac{1}{1-\alpha}\log \sum_i p_i\left(\frac{q_i}{p_i}\right)^\alpha \le \frac{1}{1-\alpha}\log\left(\sum_i q_i\right)^\alpha \left(\sum_i p_i\right)^{1-\alpha} = 0. $$

If you now take the limit $\alpha \rightarrow 1$, you get the Gibbs inequality. The inequality above can be viewed as the analogue of the Gibbs inequality but for Renyi entropy instead of Gibbs or Shannon entropy.

Answer 5

You can look at the more general inequality:

$$ \sum_i a_i f(\frac{b_i}{a_i}) \leq a f(\frac{b}{a}) $$ where $a = \sum_i a_i$, and $b=\sum_i b_i$, for $f$ any concave function.

The intuition (and proof) of the general inequality is in the paper:

GJ Woeginger. When Cauchy and Hölder Met Minkowski: A Tour through Well-Known Inequalities.

Plugging in the logarithm for $f$ gives Gibbs' inequality.

Answer 6

Tom, the result follows trivially from the fact that $x \mapsto x \log x$ is convex. That fact seems pretty geometric to me. Here is a modified version of the proof from Mackey (2003, pp. 7-8).

Let $i \mapsto p_i$ and $i \mapsto q_i$ be any measurable functions on some measurable space $I$. Write $H(x) := x \log x$. By convexity of the function $H$, for each $i$, we have

\begin{eqnarray} H(p_i) &\ge& H(q_i) + H'(q_i)(p_i-q_i) \\ p_i \log p_i &\ge& q_i \log q_i + (\log q_i + 1)(p_i-q_i) \\ p_i \log p_i - p_i &\ge& p_i \log q_i - q_i. \\ \end{eqnarray}

The integrated form of this is the general Gibbs inequality. i.e., if $\mu$ is any measure on $I$, then $$\int (p_i \log p_i - p_i) ~\mu(\operatorname{d} i) \ge \int (p_i \log q_i - q_i) ~\mu(\operatorname{d} i).$$

Your version of the inequality is the special case where $p$ and $q$ are probability densities with respect to a counting measure on $I$. i.e., if $\sum p_i = 1$ and $\sum q_i = 1$, then $$\sum p_i \log p_i \ge \sum p_i \log q_i $$ hence $$-\sum p_i \log q_i \ge -\sum p_i \log p_i. $$

Answer 7

This is not a geometric interpretation that you asked for, nevertheless gives an intuition about the logarithmic version of the inequality: $-\sum p_i\log p_i$ is the minimum expected number of set-membership-type questions to get to the secret that is distributed according to $\mathbf{P}=(p_1,\ldots,p_n)$. Now suppose whoever is asking the questions mistakenly thinks the distribution of the secret is $\mathbf{Q}=(q_1,\ldots,q_1)$. Then the minimum expected number of set-membership questions to get to the secret is $-\sum p_i\log q_i$. Gibb's ineq. just says that on average, you get to the secret quicker if you have the "correct" distribution than assuming anything else. (This in the language of source coding is just saying: the shortest expected code length is achieved with respect to the true distribution of the source). Hope this helps!