Gibbs-Ungleichung

In der Informationstheorie ist die Gibbs-Ungleichung, benannt nach Josiah Willard Gibbs, eine Aussage über die Entropie einer diskreten Wahrscheinlichkeitsverteilung. Man erhält mit ihr eine untere Schranke der mittleren Codewortlänge von optimalen Präfixcodes und eine untere Schranke der mittleren Laufzeit von vergleichsbasierten Sortierverfahren.

Gibbs-Ungleichung

Es seien <math>p=(p_1,\dots,p_n)</math> und <math>q=(q_1,\dots,q_n)</math> diskrete Wahrscheinlichkeitsverteilungen, d. h. <math>p_i,q_i > 0</math> für alle <math>i</math> und <math>\sum_{i=1}^np_i = \sum_{i=1}^nq_i =1</math>. Dann gilt:

<math>-\sum\limits_{i=1}^np_i\log_2p_i \leq -\sum\limits_{i=1}^np_i\log_2q_i</math>

Gleichheit tritt genau dann auf, wenn <math>p_i=q_i</math> für alle <math>i</math>.

Beweis

Für alle <math>x>0</math> gilt die Ungleichung <math>\ln x\le x-1</math>, wobei Gleichheit nur im Fall <math>x=1</math> auftritt.

Setzt man für <math>x</math> insbesondere <math>\frac{q_i}{p_i}</math> ein, so erhält man <math> \ln\left(\frac{q_i}{p_i}\right)\le \frac{q_i}{p_i}-1 \quad \forall i=1,...,n</math>.

Multipliziert man die Ungleichung mit <math>p_i</math> durch und summiert über alle <math>i</math>, so erhält man

<math>\sum_{i=1}^n p_i \ln\left(\frac{q_i}{p_i}\right)\le \sum_{i=1}^n (q_i-p_i)=\sum_{i=1}^n q_i-\sum_{i=1}^n p_i=1-1=0</math>.

Nachdem <math>\ln\left(\frac{q_i}{p_i}\right)=\ln(q_i)-\ln(p_i)</math> ist, folgt daraus

<math>\sum_{i=1}^n p_i \ln(q_i)\le \sum_{i=1}^n p_i \ln(p_i)</math>.

Bringt man die beiden Terme auf die jeweils entgegengesetzte Seite, so ist

<math>-\sum_{i=1}^n p_i \ln(p_i)\le -\sum_{i=1}^n p_i \ln(q_i)</math>.

Anstelle des natürlichen Logarithmus lässt sich genauso gut jede andere Logarithmenbasis <math>b>1</math> verwenden, da <math>\log_b(x)=\frac{\ln(x)}{\ln(b)}</math> gilt.

Man braucht die Ungleichung hierzu nur mit der positiven Zahl <math>\ln(b)</math> durchdividieren.

In der Informationstheorie bietet es sich an als Basis <math>b=2</math> zu wählen.

Folgerungen

Für die Entropie gilt

<math>H(p_1,\dots,p_n) \leq \log_2 n</math>,

mit Gleichheit genau dann, wenn <math>p_i=\frac{1}{n}</math> für alle <math>i</math>.

Wenn <math>X,Y</math> diskrete Zufallsvariablen sind, dann ist

<math>H(X,Y) \leq H(X) + H(Y)</math>,

mit Gleichheit genau dann wenn <math>X</math> und <math>Y</math> stochastisch unabhängig sind.

Einige nützliche Anwendungen ergeben sich in Verbindung mit der Kraft-Ungleichung. Sei dazu ein vollständiger Binärbaum mit den Blatttiefen <math>\ell_1,\dots,\ell_n</math> und einer den Blättern zugeordneten Wahrscheinlichkeitsverteilung <math>p=(p_1,\dots,p_n)</math> gegeben. Dann gilt mittels <math>q_i := 2^{-\ell_i}</math>:

<math>H(p_1,\dots,p_n) \leq -\sum\limits_{i=1}^np_i\log_22^{-\ell_i} = \sum\limits_{i=1}^np_i\ell_i</math>

Die mittlere Blatttiefe ist also von unten durch die Entropie der dazugehörigen Wahrscheinlichkeitsverteilung beschränkt.

Damit ist dann klar, dass die mittlere Codewortlänge eines optimalen Präfixcodes von unten durch die Entropie der zugehörigen Wahrscheinlichkeitsverteilung der Symbole beschränkt ist. Gleichheit tritt hier genau dann auf, wenn <math>p_i = 2^{-\ell_i}</math> für alle <math>i</math> gilt, wobei <math>\ell_i</math> die Codewortlänge des <math>i</math>-ten Codewortes bezeichnet.

Bei vergleichsbasierten Sortierverfahren von <math>n</math> Elementen unter Gleichverteilungsannahme ergibt sich durch Betrachtung der mittleren Blatttiefe des binären Entscheidungsbaums die untere Schranke <math>\log_2n!</math>. Die average-case-Laufzeit eines vergleichsbasierten Sortierverfahrens verhält sich also asymptotisch wie <math>n\log n</math>.

Literatur

• U. Schöning: Algorithmik. Spektrum Akademischer Verlag, Heidelberg 2001.
• E. Becker, W. Bürger: Kontinuumsmechanik. Eine Einführung in die Grundlagen und einfache Anwendungen, B.G. Teubner Verlag, Stuttgart 1975.
• Hermann Rohling: Einführung in die Informations- und Codierungstheorie. B.G. Teubner Verlag, Stuttgart 1995, ISBN 3-519-06174-0.

Weblinks

• Die Entropie Funktion (abgerufen am 12. Februar 2018)
• Gibbssche Punktprozesse (abgerufen am 12. Februar 2018)
• Informations- und Codierungstheorie (abgerufen am 12. Februar 2018)
• Neue Matrix-Ungleichungen und Anwendungen auf konstitutive Beziehungen in der nichtlinearen Elastizitätstheorie (abgerufen am 12. Februar 2018)
• Gibbs Masse und Zufallsfelder (abgerufen am 12. Februar 2018)