The log sum inequality is used for proving theorems in
information theory.
Statement
Let
and
be nonnegative numbers. Denote the sum of all
s by
and the sum of all
s by
. The log sum inequality states that
:
with equality if and only if
are equal for all
, in other words
for all
.
(Take
to be
if
and
if
. These are the limiting values obtained as the relevant number tends to
.)
Proof
Notice that after setting
we have
:
where the inequality follows from
Jensen's inequality since
,
, and
is convex.
Generalizations
The inequality remains valid for
provided that
and
.
The proof above holds for any function
such that
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
and
are positive real numbers with
and
, and
, then
.
Applications
The log sum inequality can be used to prove inequalities in information theory.
Gibbs' inequality 200px, Josiah Willard Gibbs
In information theory, Gibbs' inequality is a statement about the information entropy of a discrete probability distribution. Several other bounds on the entropy of probability distributions are derived from Gibbs' inequ ...
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.
:
The inequality can also prove convexity of Kullback-Leibler divergence.
Notes
References
*
*
* T.S. Han, K. Kobayashi, ''Mathematics of information and coding.'' American Mathematical Society, 2001. .
* Information Theory course materials, Utah State Universit
Retrieved on 2009-06-14.
* {{cite book , last=MacKay, first=David J.C. , author-link=David J. C. MacKay, url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html, title=Information Theory, Inference, and Learning Algorithms, publisher=Cambridge University Press, year=2003, isbn=0-521-64298-1
Inequalities
Information theory
Articles containing proofs