Misplaced Pages

Revision as of 23:44, 12 January 2023

The log sum inequality is used for proving 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}$, in other words ${\displaystyle a_{i}=cb_{i}}$ for all ${\displaystyle i}$.

(Take ${\displaystyle a_{i}\log {\frac {a_{i}}{b_{i}}}}$ to be ${\displaystyle 0}$ if ${\displaystyle a_{i}=0}$ and ${\displaystyle \infty }$ if ${\displaystyle a_{i}>0,b_{i}=0}$. These are the limiting values obtained as the relevant number tends to ${\displaystyle 0}$.)

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=1}^{n}{\frac {b_{i}}{b}}=1}$, and ${\displaystyle f}$ is convex.

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 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 ${\displaystyle a_{1},a_{2}\cdots a_{n}}$ and ${\displaystyle b_{1},b_{2}\cdots b_{n}}$ are positive real numbers with ${\displaystyle a_{1}+a_{2}\cdots +a_{n}=a}$ and ${\displaystyle b_{1}+b_{2}\cdots +b_{n}=b}$, and ${\displaystyle k\geq 0}$, then ${\displaystyle \sum _{i=1}^{n}a_{i}\left(\log {\frac {a_{i}}{b_{i}}}\right)\geq a\log \left({\frac {a}{b}}+k\right)}$.

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

Proof

Let ${\displaystyle P=(p_{i})_{i\in \mathbb {N} }}$ and ${\displaystyle Q=(q_{i})_{i\in \mathbb {N} }}$ be pmfs. In the log sum inequality, substitute ${\displaystyle n=\infty }$, ${\displaystyle a_{i}=p_{i}}$ and ${\displaystyle b_{i}=q_{i}}$ to get ${\displaystyle \mathbb {D} _{\mathrm {KL} }(P\|Q)\equiv \sum _{i}p_{i}\log _{2}{\frac {p_{i}}{q_{i}}}\geq 1\log {\frac {1}{1}}=0}$ with equality if and only if ${\displaystyle p_{i}=q_{i}}$ for all i (as both ${\displaystyle P}$ and ${\displaystyle Q}$ sum to 1).

The inequality can also prove convexity of Kullback-Leibler divergence.

Notes

1. ^ Cover & Thomas (1991), p. 29.
2. F. M. Dannan, P. Neff, C. Thiel (2016). "On the sum of squared logarithms inequality and related inequalities" (PDF). Journal of Mathematical Inequalities. 10 (1). doi:10.7153/jmi-10-01. Retrieved 12 January 2023.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. MacKay (2003), p. 34.
4. Cover & Thomas (1991), p. 30.

References

• Cover, Thomas M.; Thomas, Joy A. (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9.
• Csiszár, I.; Shields, P. (2004). "Information Theory and Statistics: A Tutorial" (PDF). Foundations and Trends in Communications and Information Theory. 1 (4): 417–528. doi:10.1561/0100000004. Retrieved 2009-06-14.
• T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. ISBN 0-8218-0534-7.
• Information Theory course materials, Utah State University . Retrieved on 2009-06-14.
• MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.

• Inequalities
• Information theory