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{aligned}\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 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{aligned}}

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

\mathbb {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.

This article is issued from Wikipedia - version of the 6/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.