log sum inequality
   HOME

TheInfoList



OR:

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_is by a and the sum of all b_is 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 200px, Josiah Willard Gibbs In information theory, Gibbs' inequality is a statement about the information entropy of a discrete probability distribution. Several other bounds on the entropy of probability distributions are derived from Gibbs' inequ ...
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 Information theory Articles containing proofs