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

Statement

Let and 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 with equality if and only if are equal for all i, in other words a_i =c b_i for all i. (Take to be 0 if a_i=0 and \infty if . These are the limiting values obtained as the relevant number tends to 0.)

Proof

Notice that after setting we have where the inequality follows from Jensen's inequality since, , 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 and are positive real numbers with and, and k \geq 0, 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. !Proof with equality if and only if p_i=q_i for all i (as both P and Q sum to 1). The inequality can also prove convexity of Kullback-Leibler divergence.