Entropie (Informationstheorie)

Entropie (nach dem Kunstwort ἐντροπία) ist in der Informationstheorie ein Maß, welches für eine Nachrichtenquelle den mittleren Informationsgehalt ausgegebener Nachrichten angibt. Der Begriff ist eng verwandt mit der Entropie in der Thermodynamik und statistischen Mechanik.

Das informationstheoretische Verständnis des Begriffes Entropie geht auf Claude E. Shannon zurück und existiert seit etwa 1948. In diesem Jahr veröffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prägte damit die moderne Informationstheorie.

Die Entropie wird üblicherweise mit einem großen Eta ($\mathrm {H}$) bezeichnet.

Definition

Claude Elwood Shannon definierte die Entropie $\mathrm {H}$ einer diskreten, gedächtnislosen Quelle (diskreten Zufallsvariable) $X$ über einem endlichen, aus Zeichen bestehenden Alphabet $Z=\{z_{1},z_{2},\dots ,z_{m}\}$ wie folgt: Zunächst ordnet man jeder Wahrscheinlichkeit $p$ eines Ereignisses seinen Informationsgehalt $I(z)=-\log _{2}p_{z}$ zu. Dann ist die Entropie eines Zeichens definiert als der Erwartungswert des Informationsgehalts

$\mathrm {H} _{1}=E[I]=\sum _{z\in Z}p_{z}I(z)=-\sum _{z\in Z}p_{z}\log _{2}p_{z}$.

Sei $z\in Z$, dann ist $p_{z}=P(X=z)$ die Wahrscheinlichkeit, mit der das Zeichen $z$ des Alphabets auftritt, oder gleichwertig

$(1)\qquad \mathrm {H} _{1}=-\sum _{i=1}^{m}p_{i}\log _{2}p_{i}$,

mit $p_{i}=p_{z_{i}}$. Dabei wird $0\cdot \log _{2}0=0$ gesetzt (entsprechend dem Grenzwert $\lim _{x\rightarrow 0}x\log _{2}x$). Summanden mit verschwindender Wahrscheinlichkeit tragen daher aufgrund der Definition nicht zur Summe bei.

Die Entropie $\mathrm {H} _{n}$ für Wörter $w$ der Länge $n$ ergibt sich durch

$\mathrm {H} _{n}=-\sum _{w\in Z^{n}}p_{w}\log _{2}p_{w}$,

wobei $p_{w}=P(X=w)$ die Wahrscheinlichkeit ist, mit der das Wort $w$ auftritt. Die Entropie $\mathrm {H}$ ist dann der Limes $n\to \infty$ davon:

$(2)\qquad \mathrm {H} =\lim _{n\to \infty }{\frac {\mathrm {H} _{n}}{n}}$.

Wenn die einzelnen Zeichen voneinander stochastisch unabhängig sind, dann gilt $\mathrm {H} _{n}=n\mathrm {H} _{1}$ für alle $n$, also $\mathrm {H} =\mathrm {H} _{1}$ (vgl. Blockentropie).

Interpretation

Entropie ist ein Maß für den mittleren Informationsgehalt pro Zeichen einer Quelle, die ein System oder eine Informationsfolge darstellt. In der Informationstheorie spricht man bei Information ebenso von einem Maß für beseitigte Unsicherheit. Je mehr Zeichen im Allgemeinen von einer Quelle empfangen werden, desto mehr Information erhält man und gleichzeitig sinkt die Unsicherheit über das, was hätte gesendet werden können.

Je kleiner die Auftrittswahrscheinlichkeit eines Zeichens ist, desto höher ist seine Information. Andersherum ist die Information eines Zeichens gering, wenn es oft vorkommt.

Anschaulich lässt sich die Definition des Informationsgehalts wie folgt begründen: Wenn ein Ereignis, das mit Wahrscheinlichkeit $p_{i}$ eintreten kann, tatsächlich eintritt, dann wird dadurch ein konkretes Ereignis aus einer hypothetischen Menge von ${\tfrac {1}{p_{i}}}$ gleich wahrscheinlichen stochastisch unabhängigen Ereignissen ausgewählt. Um diese Anzahl von Ereignissen unterscheiden zu können, benötigt man $\log _{2}\left({\tfrac {1}{p_{i}}}\right)=-\log _{2}(p_{i})$ Binärbits. Dieser Wert gibt also den Informationsgehalt eines speziellen Ereignisses in Bits an. Gewichtet man den tatsächlichen Informationsgehalt der möglichen Ereignisse mit der jeweiligen Eintrittswahrscheinlichkeit, so erhält man den mittleren oder erwarteten Informationsgehalt eines Zeichens.

Die Einheit 1 Shannon ist definiert als der Informationsgehalt eines Ereignisses mit der Wahrscheinlichkeit $p=0{,}5$. Ein Beispiel für ein solches Ereignis ist das Ergebnis Kopf eines Münzwurfs.

Die Basis 2 für den Logarithmus ist willkürlich. Es stellt sich nur heraus, dass sich Bits (Binärziffern) technisch besonders einfach handhaben lassen. Würde eine andere Basis gewählt werden, zum Beispiel 3, so erhielte man ternäre Ziffern (Trits). Der Informationsgehalt lässt sich leicht durch Multiplikation mit dem Modulus $\log _{3}2$ von Bits auf Trits umrechnen.

Die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information (des Textes) notwendig ist, ergibt sich aus dem Produkt des durchschnittlichen Informationsgehalts eines Zeichens $I(X)=\log _{2}|Z|=\log _{2}N$ und der Anzahl $n$ der Zeichen $z$ im Informationstext: $I(X)|z|=I(X)n=n\log _{2}N$.

Shannons ursprüngliche Absicht, die Entropie als das Maß der benötigten Bandbreite eines Übertragungskanals zu nutzen, wurde schnell verallgemeinert. Die Entropie wurde generell als ein Maß für den Informationsgehalt betrachtet. Bei einer kleinen Entropie enthält der Informationstext Redundanzen oder statistische Regelmäßigkeiten.

Die Entropie ist im Allgemeinen nicht durch (1) gegeben. Beispielsweise ist die Wahrscheinlichkeit, eine 0 oder 1 in der Zeichenkette $1010101010\dots$ zu finden, genauso groß, wie in einer Zeichenkette, die durch statistisch unabhängige Ereignisse (etwa wiederholten Münzwurf) entstanden ist. Daher ist die Entropie $\mathrm {H} _{1}$ einzelner Zeichen für beide Zeichenketten gleich, obwohl die erste Kette weniger zufällig ist. Bereits Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_2} zeigt einen Unterschied: Die erste Zeichenkette liefert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_2 = 1} , die zweite liefert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_2 = 2} . Man kann das auch so deuten: Die Wahrscheinlichkeit eines Zeichens hängt vom vorangegangenen Zeichen ab. Stochastische Unabhängigkeit ist also nicht gegeben.

Für aufeinander folgende Ereignisse, die nicht stochastisch unabhängig sind, reduziert sich die Entropie aufeinander folgender abhängiger Ereignisse fortlaufend. In einem solchen Fall kann man auch mit der bedingten Entropie und der Quellentropie arbeiten, die beide auf Verbundwahrscheinlichkeiten aufbauen.

In engem Zusammenhang mit bedingter Entropie steht auch die Transinformation, welche die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen angibt.

Noch einfacher formuliert, ist die Entropie die durchschnittliche Anzahl von Entscheidungen (bits), die benötigt werden, um ein Zeichen aus einer Zeichenmenge zu identifizieren oder zu isolieren.

Es ist sinnvoll, dass ein Alphabet aus mindestens zwei verschiedenen Zeichen vorliegt. Eine Alphabetsgröße von eins bedeutet, dass man weder über neu ankommende Zeichen aus der Senderquelle neue Information erhält, noch die Unsicherheit über das vorangegangene Zeichen verringern kann.

Maximaler Entropiewert und Normierung

Möchte man ein normiertes Maß für die Entropie einer beliebigen diskreten Verteilung haben, ist es von Vorteil, die maximal mögliche Entropie, die bei Gleichverteilung der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} erreicht wird, zur Normierung heranzuziehen. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = |Z|} die Anzahl der Zeichen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} über dem Alphabet $Z$, dann ist die maximale Entropie $\mathrm {H} _{\mathrm {max} }$ gegeben wenn

$\;p_{i}={\frac {1}{|Z|}}={\frac {1}{N}}\ \forall \;p_{i}$,

dann ist $\mathrm {H} _{\mathrm {max} }=-\sum _{i=1}^{N}{{\frac {1}{N}}\log _{2}{\frac {1}{N}}}=\log _{2}{N}$.

Daraus folgt beispielsweise $\mathrm {H} _{\mathrm {max} }=1$ für eine Binärverteilung ($Z=\{0,1\}$), also benötigt man ein Bit pro Zeichen und $|I|$ Zeichen für die komplette Information $I$. Dieser Wert wird erreicht, wenn Nullen und Einsen gleich häufig vorkommen. Normiert man nun die Entropie einer beliebigen Verteilung mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = |Z|} verschiedenen Zeichen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_\mathrm{max}} erhält man:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{\Eta}{\Eta_{\mathrm{max}}} = - \sum_{i=1}^{|Z|}{p_i \cdot \frac{\log_2{p_i}}{\log_2{N}}} = - \sum_{i=1}^{|Z|}{p_i \cdot \log_N{p_i}} \leq 1}

Die so definierte normierte Entropie kann maximal den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} annehmen.

Um die Entropien von Nachrichten unterschiedlicher Länge vergleichen zu können, hat man die Entropierate eingeführt, die die Entropie auf das einzelne Zeichen bezieht (siehe dort).

Beispiele

Alphabet

Bei gleichmäßiger Verteilung kann bei einem Alphabet auf kein Zeichen verzichtet werden. Dagegen ist die Buchstabenhäufigkeit in der deutschen Sprache ungleichmäßig, siehe auch: Entropie (Kryptologie). Beispielsweise ist der Buchstabe E im Deutschen siebenmal so häufig wie M oder O, was zu Redundanz im Alphabet führt. Nun möchte man ermitteln, wie groß diese Redundanz ist.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 26} die Größe des Alphabets. Die Redundanz R berechnet sich mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = \Eta_\mathrm{max} - \Eta} . Für das deutsche Alphabet errechnet man anhand der Buchstabenhäufigkeit eine Entropie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta} von 4,0629 bit/Zeichen. Die maximale Entropie beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_\mathrm{max} = \log_2|26| = 4{,}7004} bit/Zeichen. Damit folgt eine Redundanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R = 4{,}7004 - 4{,}0629 = 0{,}6375} bit/Zeichen. Berechnet man weiter die gesamte Redundanz, die sich aus der Summe der Redundanzen eines jeden Zeichens ergibt, so erhält man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R \cdot N = 16{,}575} Bits. Nun wäre interessant zu wissen, wie vielen Zeichen dies aus unserem Alphabet entspricht. Dividiert man die redundanten Bits durch den durchschnittlichen Informationsgehalt eines gleichverteilten Zeichens, so erhält man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (R\cdot N)/\Eta_\mathrm{max} = 3{,}53} Zeichen → 3 Zeichen (ohne Redundanzen). Rechnet man allerdings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (R\cdot N)/\Eta = 4{,}08} (⇒ 4 Zeichen), so bestimmt man die Anzahl von Zeichen mit einer Redundanz, wie sie auch im Alphabet vorhanden ist.

Ohne Informationsverlust könnte das Alphabet also um vier Buchstaben reduziert werden. Diese Überlegung berücksichtigt nur die statistische Verteilung der Buchstaben. Häufige Buchstabenkombinationen wie SCH oder ST bleiben genauso unberücksichtigt (bedingte Entropie) wie gleich klingende Buchstaben (Q, K).

Münzwurf

Maximale Entropie bei p=0.5

Bei einem Münzwurf sind idealerweise Kopf oder Zahl gleich wahrscheinlich. Wenn man die Entropie als Maß für die Ungewissheit auffasst, wird sie hier einen maximalen Wert aufweisen. Es ist völlig ungewiss, ob beim nächsten Wurf Kopf oder aber Zahl geworfen wird.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} eine diskrete Zufallsvariable und der Erwartungswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle E(X)= \sum P(X=x_i)\cdot x_i} mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X=x_0) = p_0 = p = \frac{1}{2}} (Kopf) und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X=x_1) = p_1 = q = \frac{1}{2}} (Zahl),

so ergibt sich aus obiger Definition Entropie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta=1}  bit.

Anders bei einer gezinkten Münze, etwa einer Münze, die im Mittel in 60 % der Fälle Kopf und nur in 40 % der Fälle Zahl anzeigt. Die Ungewissheit ist hier geringer als bei der normalen Münze, da man eine gewisse Präferenz für Kopf hat. Gemessen als Entropie liegt die Ungewissheit bei nur noch etwa 0,971.

Die Summe der Wahrscheinlichkeiten ist immer 1.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p + q = 1}

Die Entropie lässt sich aus der Summe der Teilentropien berechnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = \Eta_p + \Eta_q = - p \cdot \log_2 p - q \cdot \log_2 q}

Ersetzt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} durch den Ausdruck Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1-p} , so erhält man die Formel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = - p \cdot \log_2 p - ( 1 - p ) \cdot \log_2 (1 - p)}

Dies kann man grafisch folgendermaßen darstellen:

Für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} kann man daraus die Entropie direkt ablesen. Die Funktion ist symmetrisch zur Geraden Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 0{,}5} . Sie fällt bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 0} steil zu einem Entropie-Wert von 0 ab. Auch bei Werten, die sich dem sicheren Ereignis von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 1} nähern, fällt die Entropie auf 0 ab.

Dieser Zusammenhang gilt jeweils für ein Zufallsereignis. Bei mehreren Zufallsereignissen muss man die einzelnen Entropien zusammenzählen und man kann so leicht Entropiewerte über 1 erreichen. Die Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} dagegen bleibt auch bei Wiederholungen definitionsgemäß immer zwischen 0 und 1.

Entropie in Abhängigkeit von der Zahl der Münzwürfe

Wiederholt man den Münzwurf zweimal, wächst die Zahl der Möglichkeiten auf vier. Die Wahrscheinlichkeit jeder einzelnen Möglichkeit liegt bei 0,25. Die Entropie des zweimaligen Münzwurfes ist dann 2 Sh. Wenn man einen idealen Münzwurf mehrfach wiederholt, dann addiert sich die Entropie einfach. Die Entropie einer Reihe von 20 idealen Münzwürfen berechnet sich einfach: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = 20 \cdot 1\; \mathrm{bit} = 20\; \mathrm{bit}} . Dies ist im Bild dargestellt.

Man kann nicht einfach aus einem Wert der Wahrscheinlichkeit die Entropie ausrechnen. Die Entropie betrifft den gesamten Zufallsprozess. Jede Teilwahrscheinlichkeit eines möglichen Ergebnisses geht in die Berechnung der Entropie des Gesamtprozesses ein. Die Angabe einer Teilentropie für jedes mögliche Ergebnis ist dabei wenig sinnvoll. In der Shannonschen Entropieformel sollte also die Summe der Wahrscheinlichkeiten 1 ergeben, sonst kann das Ergebnis missverständlich sein.

Speichert man eine Folge von Münzwürfen als Bitfolge, dann bietet es sich an, Kopf stets durch 0 und Zahl stets durch 1 zu repräsentieren (oder umgekehrt). Bei der gezinkten Münze sind kompaktere Kodierungen möglich, zum Beispiel die Huffman-Kodierung.

Idealer Würfel

Bei einem Wurf eines idealen Würfels mit sechs Möglichkeiten ist die Entropie größer als 1. Im Allgemeinen ist die Entropie größer als 1 für ein Zufallsereignis mit stochastisch unabhängigen Zufallsvariablen aus einem Zufallsexperiment mit mehr als zwei gleichberechtigten Möglichkeiten im Ergebnisraum. Ihr Wert wird bei gleich wahrscheinlichen Möglichkeiten im Ergebnisraum folgendermaßen berechnet:

Sei n die Anzahl der Möglichkeiten, dann sind die Wahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i = \tfrac{1}{n}} und die Entropie

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = \log_2\!\left(\frac{1}{p_i}\right) = \log_2(n)} .

Beim idealen Würfel sind sechs Möglichkeiten im Ergebnisraum. Daraus folgt die Entropie für einmaliges Werfen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = \log_2 6 = \log_2 (2 \cdot 3) = \log_2 2 + \log_2 3 = 1 + \log_2 3 \approx 1 + 1{,}585 = 2{,}585\; \mathrm{Sh}}

Entropie vs. Zahl der Möglichkeiten

Einfach zu berechnen ist die Entropie eines Wurfes eines idealen Achterwürfels: Er hat acht gleichberechtigte Möglichkeiten.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = \log_2 8 = 3\; \mathrm{Sh}}

Die Entropie eines Wurfes mit dem idealen Achterwürfel entspricht der Entropie von drei Würfen mit der idealen Münze.

Die Abbildung stellt den Zusammenhang zwischen der Entropie und der Zahl der gleichberechtigten Möglichkeiten eines Zufallsexperimentes dar.

Entropietests

Um zu testen, wie gut Daten komprimierbar sind, oder um Zufallszahlen zu testen, werden Entropietests verwendet. Als Zufallszahltest wird die Entropie einer bestimmten Anzahl von Zufallszahlen bestimmt und ab einem Mindestwert, beispielsweise 7 Bit je Byte, gilt er als bestanden. Allerdings gibt es viele solcher Tests, da die Entropie nicht eindeutig ist; sie kann beispielsweise bitbasiert oder bytebasiert definiert sein.

Ein einfaches Beispiel:

Eine Quelle, etwa ein Spielwürfel oder eine Münze, gebe nur die Werte 0xAA (dezimal 170) und 0x55 (dezimal 85) aus, beide mit gleicher Wahrscheinlichkeit. Bitweise ist die Ausgabe zu 50 % 0 oder 1, byteweise ist sie zu 50 % 0xAA oder 0x55. Die bitweise Entropie ist (mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \log = \log_2} )

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{\Eta}{\Eta_{\mathrm{max}}} = -1/\log(2) \cdot (1/2 \cdot \log(1/2) +1/2 \cdot \log(1/2)) = 1 }

während die byteweise Entropie mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{\Eta}{\Eta_{\mathrm{max}}} = -1/\log(256) \cdot (1/2 \cdot \log(1/2) +1/2 \cdot \log(1/2)) = 1/8}

deutlich kleiner ist.

Der Hersteller dieses Zufallszahlengenerators wird natürlich als Entropie des Geräts die bitweise Entropie, also 1, angeben. Analog wird ein Programmierer eines Kompressionsprogramms möglichst diejenige Basis wählen, bei der die Entropie minimal ist (hier Bytes), sich also die Daten am besten komprimieren lassen.

Dieses Beispiel ist wenig realistisch, da nur zwei von 256 möglichen Werten verwendet werden, aber wenn auch die anderen Bytes mit einer kleinen Wahrscheinlichkeit von beispielsweise 1/123456789 ausgegeben werden, so ändert dies an der bitweisen Entropie nichts und die byteweise wird kaum größer; sie bleibt unter 1/2. Erst mit Annäherung der Byte-Wahrscheinlichkeiten an 1/256 erreicht die byteweise Entropie den Wert 1, aber dann kann es noch Korrelationen der Bytes geben, also etwa die Folge 0xaaaa viel häufiger sein als die Folge 0x5555. Dies ist der Hauptgrund, weshalb es viele verschiedene Zufallszahlentests gibt.

Diese Mehrdeutigkeit ist nicht möglich beim Entropiebelag, da dort nicht nur über Wahrscheinlichkeiten summiert wird, sondern über ergodische Wahrscheinlichkeiten von Zuständen, Zustandsübergangswahrscheinlichkeiten und bedingte Wahrscheinlichkeiten. Berechnet wird er mit der Theorie der Markow-Kette. Allerdings ist der Rechenaufwand dafür bei realen Zufallszahlengeneratoren hoch.

Es ist wichtig zu erklären, dass Entropietests nur Gleichwahrscheinlichkeit messen, und keine echte Unvorhersehbarkeit. Der Unterschied zwischen echten Zufallszahlengeneratoren und Pseudozufallszahlengeneratoren ist unmessbar.

Datenkompression und Entropie

Die Entropiekodierung ist ein Kompressionsalgorithmus, um Daten verlustfrei zu komprimieren. In diesem Zusammenhang spielen die Kreuzentropie sowie die Kullback-Leibler-Divergenz als Maß für die durch eine schlechte Kodierung ausgelösten Verschwendungen von Bits eine Rolle.

Beispiel:

• Gegeben sei die Zeichenkette ABBCAADA (siehe auch Entropiekodierung).
• Die Buchstaben-Wahrscheinlichkeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_A= 4/8= 0{,}5} ; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_B= 0{,}25} ; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_C=p_D= 0{,}125}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = - (0{,}5\cdot\log_2{0{,}5} + 0{,}25\cdot\log_2{0{,}25} + 2\cdot(0{,}125\cdot \log_2{0{,}125})) = 1{,}75}

• Maximalentropie (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_A = p_B = p_C = p_D = 0{,}25} ):

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_\mathrm{max} = -4\cdot(0{,}25\cdot\log_2{0{,}25})= -\log_2{4^{-1}}= \log_2{4} = 2}

• Die Maximalentropie lässt sich ebenso mit der Formel der maximalen Entropie berechnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta_\mathrm{max} = \log_2{|\{A,B,C,D \}|} = \log_2{\frac{1}{p_A}} = \log_2{4} = 2}

Alternative Möglichkeiten der Informationsquantifizierung

Ein anderer Zugang, den Informationsgehalt einer Nachricht zu messen, ist durch die Kolmogorow-Komplexität gegeben, worin der kürzestmögliche Algorithmus zur Darstellung einer gegebenen Zeichenkette die Komplexität der Nachricht angibt. Ähnlich ist die Logische Tiefe definiert, die sich aber auf die Zeitkomplexität eines Algorithmus zur Erzeugung der Daten bezieht. Gregory Chaitin ist ebenfalls über die Shannonsche Definition der Entropie einer Information hinausgegangen (siehe Algorithmische Informationstheorie).

Ähnlichkeit zur Entropie in der Physik

In der Physik (siehe Thermodynamik, speziell Entropie) spielt eine gleich benannte Größe eine wesentliche Rolle. Die physikalische Entropie unterscheidet sich von der Shannon'schen Informationsentropie durch einen zusätzlichen Normierungsfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k_\mathrm{B}} , die Boltzmannsche Konstante, und durch die Ersetzung der im Logarithmus benutzten Basis (der duale Logarithmus wird durch den natürlichen Logarithmus ersetzt). Somit unterscheiden sich physikalische Entropie und mathematische Entropie durch den positiven Umrechnungsfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k_\mathrm{B} \ln 2 } , versehen mit seiner physikalischen Einheit. Der Zusammenhang wurde durch ein Maxwellscher Dämon genanntes Gedankenexperiment hergestellt.

Siehe auch

• Auffälligkeit (Informationstheorie)
• Blockentropie
• Differentielle Entropie für kontinuierliche Verteilungen
• Entropie (Kryptologie)
• Entropieschätzung
• Quellentropie
• Rényi-Entropie
• Transinformation und Kullback-Leibler-Divergenz

Literatur

• C. E. Shannon: A Mathematical Theory of Communication. In: Bell System Technical Journal. Band 27, Nr. 3, 1948, S. 379–423, doi:10.1002/j.1538-7305.1948.tb01338.x (PDF). 
• Claude Elwood Shannon und Warren Weaver: The Mathematical Theory of Communication, University of Illinois Press 1963, ISBN 0-252-72548-4 (Softcover) und ISBN 0-252-72546-8 (Hardcover)
• Rolf Johannesson: Informationstheorie, Addison-Wesley 1992, ISBN 3-89319-465-7
• Norbert Bischof: Struktur und Bedeutung, 1998, ISBN 3-456-83080-7 (Das Buch ist für Sozialwissenschaftler geschrieben und erklärt mathematische Zusammenhänge Nicht-Mathematikern in sehr verständlicher Weise. Das Kapitel 2 widmet sich der Informationstheorie.)
• Sven P. Thoms: Ursprung des Lebens. Fischer, Frankfurt a. M. 2005, ISBN 3-596-16128-2 (Das Buch ist aus biologischer und chemischer Perspektive geschrieben. Ein Kapitel behandelt den Zusammenhang von Leben und Entropie.)
• Thomas Cover: Elements of Information Theory, Wiley-Interscience 2006, ISBN 0-471-24195-4 (Das Buch ist nur auf Englisch erhältlich. Es behandelt ausführlich die Informationstheorie und ist mathematisch gehalten.)
• Martin Werner: Information und Codierung, Vieweg 2002, ISBN 3-528-03951-5

Weblinks

Wikibooks: Zusammenhang zwischen Entropie und Information – Lern- und Lehrmaterialien

• Einführung der Entropie als Gesamtzufallsmenge mit vielen Beispielen und Erklärungen zur Formel von Shannon
• Entropie und Information
• Owen Maroney: Information Processing and Thermodynamic Entropy. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy.
• Shannon entropie Rechner (Text) (englisch)
• Shannon entropie Rechner (Binary) (englisch)