log sum inequality

The log sum inequality is used for proving theorems in information theory.

Statement

Let $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ be nonnegative numbers. Denote the sum of all $a_i$s by $a$ and the sum of all $b_i$s by $b$. The log sum inequality states that

:$\sum_^n a_i\log\frac\geq a\log\frac,$

with equality if and only if $\frac$ are equal for all $i$, in other words $a_i =c b_i$ for all $i$.

(Take $a_i\log \frac$ to be $0$ if $a_i=0$ and $\infty$ if $a_i>0, b_i=0$. These are the limiting values obtained as the relevant number tends to $0$.)

Proof

Notice that after setting $f(x)=x\log x$ we have

:$\begin \sum_^n a_i\log\frac & = \sum_^n b_i f\left(\frac\right) = b\sum_^n \frac f\left(\frac\right) \\ & \geq b f\left(\sum_^n \frac\frac\right) = b f\left(\frac\sum_^n a_i\right) = b f\left(\frac\right) \\ & = a\log\frac, \end$
where the inequality follows from Jensen's inequality since $\frac\geq 0$, $\sum_^n\frac= 1$, and $f$ is convex.

Generalizations

The inequality remains valid for $n=\infty$ provided that $a<\infty$ and $b<\infty$.
The proof above holds for any function $g$ such that $f(x)=xg(x)$ is convex, such as all continuous non-decreasing functions. Generalizations to non-decreasing functions other than the logarithm is given in Csiszár, 2004.

Another generalization is due to Dannan, Neff and Thiel, who showed that if $a_1, a_2 \cdots a_n$ and $b_1, b_2 \cdots b_n$ are positive real numbers with $a_1+ a_2 \cdots +a_n=a$ and $b_1 + b_2 \cdots +b_n=b$, and $k \geq 0$, then $\sum_^n a_i \log\left( \frac +k \right) \geq a\log \left(\frac+k\right)$.

Applications

The log sum inequality can be used to prove inequalities in information theory. Gibbs' inequality states that the Kullback-Leibler divergence is non-negative, and equal to zero precisely if its arguments are equal. One proof uses the log sum inequality.

:

The inequality can also prove convexity of Kullback-Leibler divergence.

Notes

References

*
*
* T.S. Han, K. Kobayashi, ''Mathematics of information and coding.'' American Mathematical Society, 2001. .
* Information Theory course materials, Utah State Universit

Retrieved on 2009-06-14.
* {{cite book , last=MacKay, first=David J.C. , author-link=David J. C. MacKay, url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html, title=Information Theory, Inference, and Learning Algorithms, publisher=Cambridge University Press, year=2003, isbn=0-521-64298-1

Inequalities (mathematics)
Information theory
Articles containing proofs