Log sum inequality

Statement

Let a 1 , … , a n and b 1 , … , 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

with equality if and only if a i b i are equal for all i .

Proof

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

where the inequality follows from Jensen's inequality since b i b ≥ 0 , ∑ i 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

Generalizations

The inequality remains valid for n = ∞ provided that a < ∞ and b < ∞ . The proof above holds for any function g such that f ( x ) = x g ( x ) is convex, such as all continuous non-decreasing functions. Generalizations to convex functions other than the logarithm is given in Csiszár, 2004.