Jump to content

Log sum inequality

From Wikipedia, the free encyclopedia

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

Statement

[edit]

Let a1,…,an and b1,…,bn be nonnegative numbers. Denote the sum of all ais by a and the sum of all bis by b. The log sum inequality states that

∑i=1nailog⁡aibi≥alog⁡ab,

with equality if and only if aibi=ab for all i.[1]

(Take ailog⁡aibi to be 0 if ai=0 and ∞ if ai>0,bi=0. These are the limiting values obtained as the relevant number tends to 0.)[1]

Proof

[edit]

Notice that after setting f(x)=xlog⁡x we have

∑i=1nailog⁡aibi=∑i=1nbif(aibi)=b∑i=1nbibf(aibi)≥bf(∑i=1nbibaibi)=bf(1b∑i=1nai)=bf(ab)=alog⁡ab,

where the inequality follows from Jensen's inequality since bib≥0, ∑i=1nbib=1, and f is convex.[1]

Generalizations

[edit]

The inequality remains valid for n=∞ provided that a<∞ and b<∞.[citation needed] 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 a1,a2⋯an and b1,b2⋯bn are positive real numbers with a1+a2⋯+an=a and b1+b2⋯+bn=b, and k≥0, then ∑i=1nailog⁡(aibi+k)≥alog⁡(ab+k). [2]

Applications

[edit]

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.[3] One proof uses the log sum inequality.

The inequality can also prove convexity of Kullback–Leibler divergence.[4]

Notes

[edit]
  1. 1 2 3 4 Cover & Thomas (1991), p. 29.
  2. ↑ F. M. Dannan, P. Neff, C. Thiel (2016). "On the sum of squared logarithms inequality and related inequalities" (PDF). Journal of Mathematical Inequalities. 10 (1): 1–17. doi:10.7153/jmi-10-01. S2CID 23953925. Retrieved 12 January 2023.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ↑ MacKay (2003), p. 34.
  4. ↑ Cover & Thomas (1991), p. 30.

References

[edit]