Gibbs' inequality

In information theory , the Gibbs inequality (according to JW Gibbs ) is a statement about the entropy of a discrete probability distribution . It is used to obtain a lower limit for the mean code word length of optimal prefix codes and a lower limit for the mean transit time of comparison-based sorting methods .

Gibbs' inequality

Let and be discrete probability distributions, i.e. H. for everyone and . Then: ${\displaystyle p=(p_{1},\dots ,p_{n})}$ ${\displaystyle q=(q_{1},\dots ,q_{n})}$ ${\displaystyle p_{i},q_{i}>0}$ ${\displaystyle i}$ ${\displaystyle \sum _{i=1}^{n}p_{i}=\sum _{i=1}^{n}q_{i}=1}$

${\displaystyle -\sum \limits _{i=1}^{n}p_{i}\log _{2}p_{i}\leq -\sum \limits _{i=1}^{n}p_{i}\log _{2}q_{i}}$

Equality occurs if and only for everyone . ${\displaystyle p_{i}=q_{i}}$ ${\displaystyle i}$

proof

The inequality applies to all , with equality only occurring in the case . ${\displaystyle x>0}$ ${\displaystyle \ln x\leq x-1}$ ${\displaystyle x=1}$

If you put in for in particular , you get . ${\displaystyle x}$ ${\displaystyle {\frac {q_{i}}{p_{i}}}}$ ${\displaystyle \ln \left({\frac {q_{i}}{p_{i}}}\right)\leq {\frac {q_{i}}{p_{i}}}-1\quad \forall i=1,...,n}$

If you multiply the inequality by and add up over all , you get ${\displaystyle p_{i}}$ ${\displaystyle i}$

${\displaystyle \sum _{i=1}^{n}p_{i}\ln \left({\frac {q_{i}}{p_{i}}}\right)\leq \sum _{i=1}^{n}(q_{i}-p_{i})=\sum _{i=1}^{n}q_{i}-\sum _{i=1}^{n}p_{i}=1-1=0}$.

After is, it follows ${\displaystyle \ln \left({\frac {q_{i}}{p_{i}}}\right)=\ln(q_{i})-\ln(p_{i})}$

${\displaystyle \sum _{i=1}^{n}p_{i}\ln(q_{i})\leq \sum _{i=1}^{n}p_{i}\ln(p_{i})}$.

If the two terms are brought to the opposite side, then is

${\displaystyle -\sum _{i=1}^{n}p_{i}\ln(p_{i})\leq -\sum _{i=1}^{n}p_{i}\ln(q_{i})}$.

Instead of the natural logarithm, any other base of logarithms can just as well be used, as applies. ${\displaystyle b>1}$ ${\displaystyle \log _{b}(x)={\frac {\ln(x)}{\ln(b)}}}$

You only need to divide the inequality by the positive number . ${\displaystyle \ln(b)}$

In information theory, it makes sense to choose as a basis . ${\displaystyle b=2}$

Inferences

The following applies to entropy

${\displaystyle H(p_{1},\dots ,p_{n})\leq \log _{2}n}$,

with equality if and only for all . ${\displaystyle p_{i}={\frac {1}{n}}}$ ${\displaystyle i}$

If are discrete random variables then is ${\displaystyle X,Y}$

${\displaystyle H(X,Y)\leq H(X)+H(Y)}$,

with equality if and only if and are stochastically independent . ${\displaystyle X}$ ${\displaystyle Y}$

Some useful applications arise in connection with the force inequality . To do this, let a complete binary tree with the leaf depths and a probability distribution assigned to the leaves be given. Then by means of : ${\displaystyle \ell _{1},\dots ,\ell _{n}}$ ${\displaystyle p=(p_{1},\dots ,p_{n})}$ ${\displaystyle q_{i}:=2^{-\ell _{i}}}$

${\displaystyle H(p_{1},\dots ,p_{n})\leq -\sum \limits _{i=1}^{n}p_{i}\log _{2}2^{-\ell _{i}}=\sum \limits _{i=1}^{n}p_{i}\ell _{i}}$

The mean leaf depth is therefore limited from below by the entropy of the associated probability distribution.

It is then clear that the mean code word length of an optimal prefix code is limited from below by the entropy of the associated probability distribution of the symbols. Equality occurs here precisely when applies to all , where the code word length denotes the -th code word. ${\displaystyle p_{i}=2^{-\ell _{i}}}$ ${\displaystyle i}$ ${\displaystyle \ell _{i}}$ ${\displaystyle i}$

In the case of comparison-based sorting methods of elements under the assumption of uniform distribution, the lower limit results from considering the mean leaf depth of the binary decision tree . The average-case runtime of a comparison-based sorting method behaves asymptotically like . ${\displaystyle n}$ ${\displaystyle \log _{2}n!}$ ${\displaystyle n\log n}$

literature

• U. Schöning: Algorithmics . Spectrum Academic Publishing House, Heidelberg 2001.
• E. Becker, W. Bürger: Continuum Mechanics. An introduction to the basics and simple applications, BG Teubner Verlag, Stuttgart 1975.
• Hermann Rohling: Introduction to information and coding theory . BG Teubner Verlag, Stuttgart 1995, ISBN 3-519-06174-0 .

Web links

• The entropy function (accessed February 12, 2018)
• Gibbs point processes (accessed February 12, 2018)
• Information and Coding Theory (accessed February 12, 2018)
• New matrix inequalities and applications to constitutive relationships in nonlinear elasticity theory (accessed February 12, 2018)
• Gibbs Mass and Random Fields (accessed February 12, 2018)