Gibbs' inequality

Gibbs' inequality

In information theory, Gibbs' inequality is a statement about the mathematical entropy of a discrete probability distribution. Several other bounds on the entropy of probability distributions are derived from Gibbs' inequality, including Fano's inequality.

It was first presented by J. Willard Gibbs in the 19th century.__NOTOC__

Gibbs' inequality

Suppose that

: P = { p_1 , ldots , p_n }

is a probability distribution. Then for any other probability distribution

: Q = { q_1 , ldots , q_n }

the following inequality between positive quantities (since the pi and qi are positive numbers less than one) holds

: - sum_{i=1}^n p_i log_2 p_i leq - sum_{i=1}^n p_i log_2 q_i

with equality if and only if

: p_i = q_i ,

for all "i".

Note that the use of base-2 logarithms is optional, and allows one to refer to the quantity on each side of the inequality as an "average surprisal" measured in bits. The difference between the two quantities is the negative of the Kullback–Leibler divergence or relative entropy, so the inequality can also be written:

: D_{mathrm{KL(Q|P) equiv - sum_{i=1}^n p_i ln frac{q_i}{p_i} geq 0

Proof

Since

: log_2 a = frac{ ln a }{ ln 2 }

it is sufficient to prove the statement using the natural logarithm (ln). Note that the natural logarithm satisfies

: ln x leq x-1

for all "x" with equality if and only if "x=1".

Let I denote the set of all i for which "pi" is non-zero. Then

:egin{align}- sum_{i in I} p_i ln frac{q_i}{p_i} & {} geq - sum_{i in I} p_i left( frac{q_i}{p_i} - 1 ight) \& {} = - sum_{i in I} q_i + sum_{i in I} p_i \& {} = - sum_{i in I} q_i + 1 \& {} geq 0end{align}

So

: - sum_{i in I} p_i ln q_i geq - sum_{i in I} p_i ln p_i

and then trivially

: - sum_{i=1}^n p_i ln q_i geq - sum_{i=1}^n p_i ln p_i

since the right hand side does not grow, but the left hand side may grow or may stay the same.

For equality to hold, we require:
# frac{q_i}{p_i} = 1 for all i in I so that the approximation ln frac{q_i}{p_i} = frac{q_i}{p_i} -1 is exact.
# sum_{i in I} q_i = 1 so that equality continues to hold between the third and fourth lines of the proof.

This can happen if and only if

:p_i = q_i

for "i" = 1, ..., "n".

Alternative proofs

The result can alternatively be proved using Jensen's inequality or log sum inequality.

Corollary

The entropy of P is bounded by:

:H(p_1, ldots , p_n) leq log n

The proof is trivial - simply set q_i = 1/n for all "i".

ee also

*Information entropy
*Fano's inequality


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Gibbs — may refer to:People*Cecil Armstrong Gibbs, composer *Cory Gibbs, soccer player *Frederic A. Gibbs, neurologist *George Gibbs (mineralogist), (1776 1833) *George Gibbs (geologist), (1815 1873) *Herschelle Gibbs, South African cricketer *Humphrey… …   Wikipedia

  • Jensen's inequality — In mathematics, Jensen s inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906 [Jensen, J. Sur les fonctions… …   Wikipedia

  • Josiah Willard Gibbs — Infobox Scientist box width = 300px name = J. Willard Gibbs image size = 300px caption = Josiah Willard Gibbs birth date = birth date|1839|2|11|mf=y birth place = New Haven, Connecticut, USA death date = death date and… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Kullback–Leibler divergence — In probability theory and information theory, the Kullback–Leibler divergence[1][2][3] (also information divergence, information gain, relative entropy, or KLIC) is a non symmetric measure of the difference between two probability distributions P …   Wikipedia

  • Inequalities in information theory — Inequalities are very important in the study of information theory. There are a number of different contexts in which these inequalities appear.hannon type inequalitiesConsider a finite collection of finitely (or at most countably) supported… …   Wikipedia

  • List of inequalities — This page lists Wikipedia articles about named mathematical inequalities. Inequalities in pure mathematics =Analysis= * Askey–Gasper inequality * Bernoulli s inequality * Bernstein s inequality (mathematical analysis) * Bessel s inequality *… …   Wikipedia

  • Shannon's source coding theorem — In information theory, Shannon s source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy.The source coding theorem shows that (in the limit, as… …   Wikipedia

  • Inégalité de Jensen — En mathématiques, et plus précisément en analyse, l’inégalité de Jensen est une relation utile et très générale concernant les fonctions convexes, due au mathématicien danois Johan Jensen et dont il donna la preuve en 1906[1]. On peut l écrire de …   Wikipédia en Français

  • Information theory and measure theory — Measures in information theory = Many of the formulas in information theory have separate versions for continuous and discrete cases, i.e. integrals for the continuous case and sums for the discrete case. These versions can often be generalized… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”