Log sum inequality

Template:Short description The log sum inequality is used for proving theorems in information theory.

Statement

Let $a_1,\dots ,a_n$ and $b_1,\dots ,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}\ge a\log \frac{a}{b},$

with equality if and only if $\frac{a_i}{b_i}=\frac{a}{b}$ for all $i$.Template:Sfnp

(Take $a_i\log \frac{a_i}{b_i}$ to be $0$ if $a_i=0$ and $\mathrm{\infty }$ if $a_i>0,b_i=0$. These are the limiting values obtained as the relevant number tends to $0$.)Template:Sfnp

Proof

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

$\begin{array}{cc}\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)\\ & \ge bf\left(\sum _{i=1}^n\frac{b_i}{b}\frac{a_i}{b_i}\right)=bf\left(\frac{1}{b}\sum _{i=1}^n{a}_i\right)=bf\left(\frac{a}{b}\right)\\ & =a\log \frac{a}{b},\end{array}$

where the inequality follows from Jensen's inequality since $\frac{b_i}{b}\ge 0$, $\sum _{i=1}^n\frac{b_i}{b}=1$, and $f$ is convex.Template:Sfnp

Generalizations

The inequality remains valid for $n=\mathrm{\infty }$ provided that $a<\mathrm{\infty }$ and $b<\mathrm{\infty }$.Template:Cn 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 $a_1,a_2\cdots a_n$ and $b_1,b_2\cdots b_n$ are positive real numbers with $a_1+a_2\cdots +a_n=a$ and $b_1+b_2\cdots +b_n=b$, and $k\ge 0$, then $\sum _{i=1}^n{a}_i\log (\frac{a_i}{b_i}+k)\ge a\log (\frac{a}{b}+k)$.

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.Template:Sfnp One proof uses the log sum inequality.

ProofTemplate:Sfnp
Let $P=(p_i{)}_{i\in \mathbb{N}}$ and $Q=(q_i{)}_{i\in \mathbb{N}}$ be pmfs. In the log sum inequality, substitute $n=\mathrm{\infty }$, $a_i=p_i$ and $b_i=q_i$ to get ${𝔻}_{\mathrm{K}\mathrm{L}}(P\Vert Q)\equiv \sum _i{p}_i{\log }_2\frac{p_i}{q_i}\ge 1\log \frac{1}{1}=0$ 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.Template:Sfnp

References

• Template:Cite book
• Template:Cite journal
• T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. Template:Isbn.
• Information Theory course materials, Utah State University [1]. Retrieved on 2009-06-14.
• Template:Cite book