# Log sum inequality

Jump to: navigation, search

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

## Statement

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

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

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

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.