The log sum inequality is used for proving theorems in information theory.
Statement Let and be nonnegative numbers. Denote the sum of all s by and the sum of all s by . The log sum inequality states that
with equality if and only if for all .
(Take to be if and if . These are the limiting values obtained as the relevant number tends to .)
Proof Notice that after setting we have
where the inequality follows from Jensen's inequality since , , and is convex.
Generalizations The inequality remains valid for provided that and . The proof above holds for any function such that 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 and are positive real numbers with and , and , then .
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.
{| class="toccolours collapsible collapsed" width="80%" style="text-align:left" !Proof |- |Let and be pmfs. In the log sum inequality, substitute , and to get
with equality if and only if for all i (as both and sum to 1).
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 University . Retrieved on 2009-06-14.