# Log sum inequality

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

## Statement

Let ${\displaystyle a_{1},\ldots ,a_{n}}$ and ${\displaystyle b_{1},\ldots ,b_{n}}$ be nonnegative numbers. Denote the sum of all ${\displaystyle a_{i}\;}$s by ${\displaystyle a}$ and the sum of all ${\displaystyle b_{i}\;}$s by ${\displaystyle b}$. The log sum inequality states that

${\displaystyle \sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}\geq a\log {\frac {a}{b}},}$

with equality if and only if ${\displaystyle {\frac {a_{i}}{b_{i}}}}$ are equal for all ${\displaystyle i}$.

## Proof

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

{\displaystyle {\begin{aligned}\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 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{aligned}}}

where the inequality follows from Jensen's inequality since ${\displaystyle {\frac {b_{i}}{b}}\geq 0}$, ${\displaystyle \sum _{i}{\frac {b_{i}}{b}}=1}$, and ${\displaystyle 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 ${\displaystyle p_{i}\;}$s for ${\displaystyle a_{i}\;}$s, and ${\displaystyle q_{i}\;}$s for ${\displaystyle b_{i}\;}$s to get

${\displaystyle \mathbb {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 ${\displaystyle n=\infty }$ provided that ${\displaystyle a<\infty }$ and ${\displaystyle b<\infty }$. The proof above holds for any function ${\displaystyle g}$ such that ${\displaystyle f(x)=xg(x)}$ is convex, such as all continuous non-decreasing functions. Generalizations to convex functions other than the logarithm is given in Csiszár, 2004.