Log sum inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Statement[edit]

Let a_1,\ldots,a_n and b_1,\ldots,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

\sum_{i=1}^n a_i\log\frac{a_i}{b_i}\geq a\log\frac{a}{b},

with equality if and only if \frac{a_i}{b_i} are equal for all i.

Proof[edit]

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


\begin{align}
\sum_{i=1}^n a_i\log\frac{a_i}{b_i} & {} = \sum_{i=1}^n b_i f\left(\frac{a_i}{b_i}\right)
 = b\sum_{i=1}^n \frac{b_i}{b} f\left(\frac{a_i}{b_i}\right) \\
& {} \geq b f\left(\sum_{i=1}^n \frac{b_i}{b}\frac{a_i}{b_i}\right) = b f\left(\frac{1}{b}\sum_{i=1}^n a_i\right)
= b f\left(\frac{a}{b}\right) \\
& {} = a\log\frac{a}{b},
\end{align}

where the inequality follows from Jensen's inequality since \frac{b_i}{b}\geq 0, \sum_i\frac{b_i}{b}= 1, and f is convex.

Applications[edit]

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

D_{\mathrm{KL}}(P\|Q) \equiv \sum_{i=1}^n p_i \log_2 \frac{p_i}{q_i} \geq 1\log\frac{1}{1} = 0.

Generalizations[edit]

The inequality remains valid for n=\infty provided that a<\infty and b<\infty. Generalizations to convex functions other than the logarithm is given in Csiszár, 2004.

References[edit]