In mathematics, the log sum inequality is an inequality which is useful for proving several theorems in information theory

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

.

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 are equal for all .

Proof

Notice that after setting we have

where the inequality follows from Jensen's inequality

Jensen's inequality

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...

 since , , and is convex.

Applications

The log sum inequality can be used to prove several inequalities in information theory such as Gibbs' inequality

Gibbs' inequality

In information theory, Gibbs' inequality is a statement about the mathematical entropy of a discrete probability distribution. Several other bounds on the entropy of probability distributions are derived from Gibbs' inequality, including Fano's inequality....

 or the convexity of Kullback-Leibler divergence.

For example to prove Gibbs' inequality it is enough to substitute s for s, and s for s to get

Generalizations

The inequality remains valid for provided that and .
Generalizations to convex functions other than the logarithm is given in Csiszár, 2004.