Log sum inequality

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

Statement

Let $a_1,\dots ,a_n$ and $b_1,\dots ,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 _{i=1}^n{a}_i\log \frac{a_i}{b_i}\ge a\log \frac{a}{b},$

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

(Take $a_i\log \frac{a_i}{b_i}$ to be $0$ if $a_i=0$ and $\mathrm{\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{array}{rl}\sum _{i=1}^n{a}_i\log \frac{a_i}{b_i}& =\sum _{i=1}^n{b}_{i}f\left(\frac{a_i}{b_i}\right)=b\sum _{i=1}^n\frac{b_i}{b}f\left(\frac{a_i}{b_i}\right)\\ & \ge bf\left(\sum _{i=1}^n\frac{b_i}{b}\frac{a_i}{b_i}\right)=bf\left(\frac{1}{b}\sum _{i=1}^n{a}_i\right)=bf\left(\frac{a}{b}\right)\\ & =a\log \frac{a}{b},\end{array}$

where the inequality follows from Jensen's inequality since $\frac{b_i}{b}\ge 0$, $\sum _{i=1}^n\frac{b_i}{b}=1$, and $f$ is convex.

Generalizations

The inequality remains valid for $n=\mathrm{\infty }$ provided that $a<\mathrm{\infty }$ and $b<\mathrm{\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\ge 0$, then $\sum _{i=1}^n{a}_i\log (\frac{a_i}{b_i}+k)\ge a\log (\frac{a}{b}+k)$.

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.

Proof
Let $P=(p_i{)}_{i\in \mathbb{\mathbb{N}}}$ and $Q=(q_i{)}_{i\in \mathbb{\mathbb{N}}}$ be pmfs. In the log sum inequality, substitute $n=\mathrm{\infty }$, $a_i=p_i$ and $b_i=q_i$ to get ${\mathbb{𝔻}}_{\mathrm{K}\mathrm{L}}(P\Vert Q)\equiv \sum _i{p}_i{\log }_2\frac{p_i}{q_i}\ge 1\log \frac{1}{1}=0$ with equality if and only if $p_i=q_i$ for all i (as both $P$ and $Q$ sum to 1).

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

References

• Cover, Thomas M.; Thomas, Joy A. (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9. 
• "Information Theory and Statistics: A Tutorial". Foundations and Trends in Communications and Information Theory 1 (4): 417–528. 2004. doi:10.1561/0100000004. http://www.renyi.hu/~csiszar/Publications/Information_Theory_and_Statistics:_A_Tutorial.pdf. Retrieved 2009-06-14. 
• T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. ISBN 0-8218-0534-7.
• Information Theory course materials, Utah State University [1]. Retrieved on 2009-06-14.
• MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. http://www.inference.phy.cam.ac.uk/mackay/itila/book.html.