Log sum inequality

In mathematics, the log sum inequality is an inequality which is useful for proving several 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_{i=1}^n a_i\log\frac{a_i}{b_i}\geq a\log\frac{a}{b},$

with equality if and only if $\frac{a_i}{b_i}$ are equal for all $i$.

Proof

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

$\begin{align} \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) \\ & {} \geq b f\left(\sum_{i=1}^n \frac{b_i}{b}\frac{a_i}{b_i}\right) = b f\left(\frac{1}{b}\sum_{i=1}^n a_i\right) = b f\left(\frac{a}{b}\right) \\ & {} = a\log\frac{a}{b}, \end{align}$

where the inequality follows from Jensen's inequality since $\frac{b_i}{b}\geq 0$, $\sum_i\frac{b_i}{b}= 1$, and $f$ is convex.

Applications

The log sum inequality can be used to prove several inequalities in information theory such as Gibbs' inequality or the convexity of Kullback-Leibler divergence.

For example, to prove Gibbs' inequality it is enough to substitute $p_i\;$s for $a_i\;$s, and $q_i\;$s for $b_i\;$s to get

$D_{\mathrm{KL}}(P\|Q) \equiv \sum_{i=1}^n p_i \log_2 \frac{p_i}{q_i} \geq 1\log\frac{1}{1} = 0.$

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 convex functions other than the logarithm is given in Csiszár, 2004.

References

• 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 . Retrieved on 2009-06-14.
• Csiszár, I.; Shields, P. (2004). "Information Theory and Statistics: A Tutorial" (PDF). Foundations and Trends in Communications and Information Theory 1 (4): 417–528. doi:10.1561/0100000004. Retrieved 2009-06-14.