Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

5 Answers

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.

share|improve this answer
    
This is a cute argument and does answer the original question. Further, it seems to give uniqueness of the optimum for rational weights as a consequence of uniqueness in the equal weights case. Do you know if there is a way to extend the uniqueness part to arbitrary real weights? –  Noah Stein Feb 25 '13 at 14:58
    
Nice! Thanks. Nevertheless, the "trick" aspect of it means that it doesn't entirely satisfy me: what I want is to get an intuitive picture in my head which makes the result seem obvious (just as for the isoperimetric inequality). @Noah: I suspect the uniqueness part can't be extended to arbitrary real weights too easily. Indeed, in the introduction to their book Inequalities, Hardy, Littlewood and Pólya comment on this limitation of such rational-approximation arguments. –  Tom Leinster Feb 25 '13 at 23:01
add comment

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.

share|improve this answer
add comment

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}. $$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.