Log sum inequality

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

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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_{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} = \frac{a}{b} for all i . (Take a_i\log \frac{a_i}{b_i} 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{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) where the inequality follows from Jensen's inequality since \frac{b_i}{b}\geq 0 , \sum_{i=1}^n\frac{b_i}{b}= 1 , and f is convex.

Generalizations

The inequality remains valid for n=\infty provided that a and b . 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_{i=1}^n a_i \log\left( \frac{a_i}{b_i} +k \right) \geq a\log \left(\frac{a}{b}+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.

References

T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. . Information Theory course materials, Utah State University . Retrieved on 2009-06-14.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354492474 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.