Entropie: IT

Zurück zur Übersicht

Randomwalk

Entropie in der Informationstheorie und Mathematik

Entropie kann man als ein Maß für den Zufall ansehen, der in einem System oder einer Informationsfolge steckt.

Man muss bei jedem Zufallsereignis mit mehreren möglichen Folgen drei Begriffe auseinanderhalten:

• die Wahrscheinlichkeit jeder Möglichkeit
• die Zahl der Möglichkeiten (Ereignisraum eines Zufallsexperimentes)
• die informationtheoretische Entropie des Ereignisses

Dabei ist die Entropie eher verwandt mit dem Begriff Zahl der Möglichkeiten, denn Sie wird aus der Zahl der Möglichkeiten abgeleitet und nur durch das Logarithmieren kleiner und handhabbarer gemacht.

Für den idealen einmaligen Münzwurf gilt dann beispielsweise:

• Wahrscheinlichkeit jeder Möglichkeit 0,5
• Zahl der Möglichkeiten: 2
• Entropie = Log₂(2) = 1 bit

Wiederholt man den Münzwurf 2 mal, dann gilt:

• Wahrscheinlichkeit jeder Möglichkeit 0,25
• Zahl der Möglichkeiten: 4
• Entropie = Log₂(4) = 2 bit

Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide Begriffe haben Gemeinsamkeiten, sind aber nicht ohne weiteres gleich zu setzen.

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

Definition

Shannon definierte die Entropie H einer gegebenen Information I über einem Alphabet Z durch

$H(I)=-\sum _{j=1}^{|Z|}{p_{j}\cdot \log _{2}{p_{j}}}$,

wobei p_j die Wahrscheinlichkeit ist, mit der das j-te Symbol z_j des Alphabets Z im Informationstext I auftritt.

Lassen Sie sich durch diese Formel nicht so schnell verwirren. Sie kommen am besten klar mit der Formel, wenn Sie ein paar Rechenaufgaben zu dieser Formel lösen. Siehe Entropie#Rechenaufgaben

Eine andere Methode, um diese Formel zu verstehen, bietet jeder Computer mit einer Programmierumgebung. Man schreibt ein kleines Computerprogramm und läßt die Variablen in einer Schleife variieren. Schon wird einem die Sache klarer, nach dem Motto: Habe ich es nicht programmiert, dann habe ich es noch nicht verstanden.

Im Folgenden wird die Formel in ihre Einzelteile zerlegt, um sie verständlich zu machen.

Summenzeichen

Das Zeichen Σ, das Sie vielleicht noch nicht kennen, steht dabei nur für eine Summe mit mehreren Teilen.

Beispiel:

$Summe=\sum _{n=1}^{5}n=1+2+3+4+5=15$

Beispiel 2:

$Summe=\sum _{n=1}^{5}n*n=1+4+9+16+25=55$

Oder allgemein:

$Summe=\sum _{j=1}^{n}p_{j}=p_{1}+p_{2}+\dots +p_{n}$

Siehe auch http://de.wikipedia.org/wiki/Summe#Notation_mit_dem_Summenzeichen

• Siehe auch: http://de.wikibooks.org/wiki/Gambas:_Rechnen#Das_Summenzeichen__programmieren

log₂

Wenn Sie das Zeichen Logarithmus nicht verstehen , schauen Sie sich einfach einmal folgende Seite an:

• https://web.archive.org/web/20171106170359/http://www.madeasy.de/2/log.htm

Bei der Shannonschen Definition wird der binäre Logarithmus verwendet. Dieser findet sich leider nicht auf den üblichen kleinen Rechnern im PC.

Im Internet kann man ihn beispielsweise hier online berechnen:

• http://rechneronline.de/logarithmus/

als Linuxuser können Sie bc nutzen: Linux-Praxisbuch:_bc Oder folgende Programme verwenden:

• http://de.wikibooks.org/wiki/Gambas:_Rechnen#Logarithmus
  • Gambas Logarithmus Programm
• https://web.archive.org/web/20171106170359/http://www.madeasy.de/2/prglog.htm
  • VB Logarithmus Programm

Auf normalen Taschenrechnern kann man den binären Logarithmus mit dem natürlichen (ln) logarithmus berechnen: log₂x := ln(x) / ln(2)

Wahrscheinlichkeit p

In die Formel geht die Wahrscheinlichkeit p ein. Wenn Sie sich noch nicht mit Wahrscheinlichkeitswerten beschäftigt haben, dann schauen Sie einfach einmal folgende Seite an:

•  Wahrscheinlichkeit

p kann Werte zwischen 0 und 1 annehmen.

• p = 0
  • Unmögliches Ereignis

• p = 1
  • Sicheres Ereignis

• p = 0,5
  • Wahrscheinlichkeit mit einer idealen Münze Zahl oder Wappen zu werfen.

Einfaches Basicprogramm zur Errechnung von H für gleichberechtigte p Werte

load"entropie.bas

5 REM ENTROPIE FUER URNE MIT X unterscheidbaren KUGELN 
10 FOR X = 1 TO 16
20 Y = LOG(X):
24 P = 1 / X
27 ZZ = 1.44265 * LOG(X): rem binärer Logarithmus
28 H = - P * 1.44265 * LOG(P) * X
29 H = INT(H* 100 + 0.5)/100 : rem runden auf 2 Stellen nach dem Komma
30 PRINT " Zahl der Kugeln ";X
32 PRINT " Wahrscheinlichkeit ";P
33 PRINT " Entropie ";H
40 NEXT

Das Programm gibt folgendes Ergebnis aus:

Zahl der Kugeln  1 
wahrscheinlichkeit  1 
Entropie  0 
Zahl der Kugeln  2 
wahrscheinlichkeit  .5 
Entropie  1 
Zahl der Kugeln  3 
wahrscheinlichkeit  .333333333 
Entropie  1.58 
Zahl der Kugeln  4 
wahrscheinlichkeit  .25 
Entropie  2 
Zahl der Kugeln  5 
wahrscheinlichkeit  .2 
Entropie  2.32 
Zahl der Kugeln  6 
wahrscheinlichkeit  .166666667 
Entropie  2.58 
Zahl der Kugeln  7 
wahrscheinlichkeit  .142857143 
Entropie  2.81 
Zahl der Kugeln  8 
wahrscheinlichkeit  .125 
Entropie  3 
Zahl der Kugeln  9 
wahrscheinlichkeit  .111111111 
Entropie  3.17 
Zahl der Kugeln  10 
wahrscheinlichkeit  .1 
Entropie  3.32 
Zahl der Kugeln  11 
wahrscheinlichkeit  .0909090909 
Entropie  3.46 
Zahl der Kugeln  12 
wahrscheinlichkeit  .0833333333 
Entropie  3.58 
Zahl der Kugeln  13 
wahrscheinlichkeit  .0769230769 
Entropie  3.7 
Zahl der Kugeln  14 
wahrscheinlichkeit  .0714285714 
Entropie  3.81 
Zahl der Kugeln  15 
wahrscheinlichkeit  .0666666667 
Entropie  3.91 
Zahl der Kugeln  16 
wahrscheinlichkeit  .0625 
Entropie  4 

Das Programm ist identisch für verschiedene Würfel mit x gleichberechtigten Möglichkeiten.

Zahl der Möglichkeiten (Ereignisraum eines Zufallsexperimentes)

Die Bedeutung des Begriffes Entropie erschließt sich am besten, wenn man sich klarmacht, wieviele Möglichkeiten in einer Zufallsauswahl gegeben sind. Dann muss man noch unterscheiden, ob alle Möglichkeiten gleichberechtigt sind oder ob die Wahrscheinlichkeit der einzelnen Möglichkeiten unterschiedlich ist.

Beispiel: Zahl der Möglichkeiten bei einem Wurf

Münze:      Zahl der Möglichkeiten 2      gleichberechtigt
Reißnagel:  Zahl der Möglichkeiten 2      verschieden wahrscheinlich
6er Würfel: Zahl der Möglichkeiten 6      gleichberechtigt

Einheit bit

Eigentlich ist die berechnete Entropie dimensionslos. Trotzdem erhält sie eine Einheit, nämlich das bit. Die Einheit Shannon ist unüblich und hat sich nicht durchgesetzt.

H multipliziert mit der Anzahl der Zeichen im Informationstext ergibt die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information notwendig sind.

Prinzipiell lässt sich die Berechnung der Entropie auch auf andere Zahlensysteme (etwa Oktalsystem, Hexadezimalsystem) als das Binärsystem (Basis 2) übertragen. In diesem Fall wird der Logarithmus nicht zur Basis 2, sondern zur entsprechenden informationstheoretischen Basis des Zahlensystems gebildet.

Die Verallgemeinerung der Entropie für eine multivariante Zufallsvariable wird Blockentropie beziehungsweise Verbundentropie genannt.

Interpretation

Entropie ist grob gesagt ein Maß für den Zufall, der in einem System oder einer Informationsfolge steckt. Dabei ist die Einheit der Zufallsinformation 1 bit definiert als die Informationsmenge, die in einer Zufallsentscheidung eines idealen Münzwurfes enthalten ist. Ein idealer Münzwurf hat nur zwei Möglichkeiten – Wappen oder Zahl –, die beide mit der gleichen Wahrscheinlichkeit p = 0,5 auftreten.

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. Wenn die Entropie bei einer Binärentscheidung beispielsweise einen Wert von 1 hat, dann gilt die Information als zufällig. Bei einer kleinen Entropie enthält der Informationstext Redundanzen oder statistische Regelmäßigkeiten. Die Zahl $H(I)$ gibt intuitiv die durchschnittliche Information an, die in einem Symbol der Quelle enthalten ist.

Die rein statistische Berechnung der informationstheoretischen Entropie nach obiger Formel ist gleichzeitig ihre Beschränkung. Beispielsweise ist die Wahrscheinlichkeit, eine 0 oder 1 in einer geordneten Zeichenkette "1010101010..." zu finden, genauso groß, wie in einer Zeichenkette, die durch statistisch unabhängige Ereignisse (etwa wiederholten Münzwurf) entstanden ist. Daher ist Shannons Entropie für beide Zeichenketten identisch, obwohl man intuitiv die erste Kette als weniger zufällig bezeichnen muss. Eine angemessenere Definition der Entropie einer Zeichenkette liefert die bedingte Entropie und Quellentropie, die beide auf Verbundwahrscheinlichkeiten aufbauen.

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

Beispiel: Münzwurf

Bei einem Münzwurf sind idealerweise „Kopf“ oder „Zahl“ gleichwahrscheinlich. Wenn man die Entropie als Maß für die Ungewissheit auffasst, wird sie in diesem einfachen dualen System einen maximalen Wert aufweisen. Es ist völlig ungewiss, ob beim nächsten Wurf „Kopf“ oder aber „Zahl“ geworfen wird. Die Entropie wird hier als 1 bit definiert.

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.

Bei der Münze ergänzen sich die Wahrscheinlichkeiten beider Möglichkeiten zur Summe 1, da es nur zwei Möglichkeiten gibt.

$p+q=1$

Die Entropie lässt sich in diesem Fall mit Shannons Formel berechnen:

$H=-(p\cdot \log _{2}p+q\cdot \log _{2}q)$

Wenn sie den Begriff log₂ nicht verstehen ( binärer Logarithmus) , dann schauen sie sich einmal folgende Seiten durch:

• http://www.madeasy.de/2/log.htm
• http://de.wikibooks.org/wiki/Mathematik:_Schulmathematik:_Logarithmieren

Ersetzt man $q$ durch den Ausdruck $1-p$, so erhält man die Formel

$H=-(p\cdot \log _{2}p+(1-p)\cdot \log _{2}(1-p))$

Ist p = 0,5 , dann kann man H errechnen:

$H=-(0,5\cdot \log _{2}0,5+0,5\cdot \log _{2}0,5)$

H = - ( 0,5 * (-1) + 0,5 *(-1))

H = - ( - 0,5 - 0,5 )

H = 1

Wenn p verschiedene Werte zwischen 0 und 1 annehmen kann , kann man den Zusammenhang zwischen p und H grafisch folgendermaßen darstellen:

Zusammenhang zwischen Wahrscheinlichkeit und Entropie

Für jedes $p$ kann man daraus die Entropie direkt ablesen. Die Funktion ist symmetrisch zur Geraden $p=0{,}5$. Sie fällt bei $p=0$ sehr steil zu einem Entropie-Wert von 0 ab. Auch bei Werten, die sich dem sicheren Ereignis von $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 $p$ dagegen bleibt auch bei Wiederholungen definitionsgemäß immer zwischen 0 und 1!

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 bit. 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: $H=20\cdot 1\ {\mbox{bit}}=20\ {\mbox{bit}}$. Dies wird im folgenden Bild dargestellt.

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

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 macht dabei wenig Sinn. In der Shannonschen Entropieformel sollte also die Summe der Wahrscheinlichkeiten 1 ergeben, sonst kann es ein missverständliches Ergebnis geben.

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. Diese erhält man beispielsweise durch den Huffman-Kode.

Beispiel: Idealer Würfel

Bei einem Wurf eines idealen Würfels mit sechs Möglichkeiten ist die Entropie größer als 1. Allgemein ist sie größer als 1 für ein Zufallsereignis aus einem Zufallsexperiment mit mehr als zwei gleichberechtigten Möglichkeiten im Ergebnisraum. Ihr Wert wird bei gleichwahrscheinlichen Möglichkeiten im Ergebnisraum folgendermaßen berechnet:

$H=\log _{2}(\mathrm {Zahl\ der\ gleichberechtigten\ Elemente\ im\ Ergebnisraum} )$.

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

$H=\log _{2}6=\log _{2}2\cdot 3=\log _{2}2+\log _{2}3=1+\log _{2}3\approx 1+1{,}585=2{,}585\ {\mbox{bit}}$

Entropie versus Zahl der gleichberechtigten Möglichkeiten

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

$H=\log _{2}8=3\ {\mbox{bit}}$

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

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

Rechenaufgaben

Reißnagel

Reißnagel in 2 möglichen Positionen

1. Berechnen Sie die Entropie des Wurfes eines Reißnagels, dessen Wahrscheinlichkeit auf dem Rücken zu liegen p = 0,3 beträgt und dessen Wahrscheinlichkeit nicht auf dem Rücken zu liegen 0,7 beträgt. Benutzen Sie dazu die Formel von Shannon.

Der Reissnagel ist das Beispiel eines binären Zufallsgenerators mit ungleicher Zufallsverteilung p ungleich q.

• Lösung: H = 0,88
• Lösungsweg: Siehe Entropie:_Loesungen

8er Würfel

2. Berechnen Sie die Entropie des Wurfes eines idealen achter Würfels, dessen Wahrscheinlichkeit für jede Seite p = 1/8 ist.

• Lösung: H = 3
• Lösungsweg: Siehe Entropie:_Loesungen

Zwei Spielwürfel

6er Würfel

3. Berechnen Sie die Entropie des Wurfes zweier idealer sechser Würfel, die gleichzeitig geworfen werden.

• Lösung: H = 4,34 für nicht unterscheidbare Würfel
• Lösung: H = 5,169925001442 für unterscheidbare Würfel
• Lösungsweg: Entropie:_Loesungen#Aufgabe_3

Summe 2 * Würfel

4. Berechnen Sie die Summe der Entropien zweier Würfe eines idealen sechser Würfels, der 2 mal hintereinander geworfen wird.

• Lösung: H = 5,169925001442
• Lösungsweg: Entropie:_Loesungen#Aufgabe_4

Urne mit 3 Kugeln

5. Sie haben eine Urne mit einer roten , einer weißen und einer schwarzen Kugel. Die Kugeln sind beim Ziehen nicht zu unterscheiden.

• a) Berechnen Sie die Wahrscheinlichkeit des Ziehens für jede Farbe.
• b) Berechnen Sie die Entropie für einen Zug aus der Urne.
• c) Berechnen Sie die Entropie für 2 Züge aus der Urne.

• Lösung a: p = 1 /3
• Lösung b: H = 1,584962500721
• Lösung c: H = 3,169925001442 mit Zurücklegen
• Lösung c: H = 2,584962500721 ohne Zurücklegen
• Lösungsweg: Entropie:_Loesungen#Aufgabe_3

Schemazeichnung einer Urne

6er Urne mit Zurücklegen

6. Wieviel Bit an Entropie steckt in jedem Zug dieser 6er Urne unter der Voraussetzung, daß alle Kugeln gleichwahrscheinlich p = 1/6 gezogen werden ?

• Antwort: H = 2,585... bit
• Lösungsweg: Siehe Entropie:_Loesungen

6er Urne ohne Zurücklegen

7. Wie groß ist die Summe der Entropien der 6er Urne unter der Voraussetzung, daß alle Kugeln gleichwahrscheinlich p = 1/6 gezogen werden und das die Kugeln nach jedem Zug nicht mehr zurückgelegt werden? Sie ziehen bis die Urne leer ist. Berechnen Sie erst die Wahrscheinlichkeit für jeden Zug, dann die Entropie für jeden Zug und dann die Summe der Entropien.

• Lösung:H = 9,491853096329
• Lösungsweg: Siehe Entropie:_Loesungen

Lottoziehung

8. Wie groß ist die Entropie einer fiktiven Lottoziehung 1 aus 1 Million Möglichkeiten.

• Lösung:H = 19,931568569324
• Lösungsweg: Siehe Entropie:_Loesungen

Kartenspiel

Alle Karten eines normalen Kartenspiels

9. Sie haben ein normales Kartenspiel mit 4 Farben und 13 Karten je Farbe (As, 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König). Die Karten werden ausführlich gemischt. Wie groß ist die Entropie beim Zug einer Karte ? Beachten Sie dazu die Zahl der gleichberechtigten Möglichkeiten und berechnen Sie dann die Entropie.

• Lösung:H = 5,70043971814109
• Lösungsweg: Siehe Entropie:_Loesungen

9a. Sie haben ein Kartenspiel mit 4 Farben und 9 Karten je Farbe. Gesamtzahl der Karten 36.Die Karten werden ausführlich gemischt. Wie groß ist die Entropie beim Zug einer Karte ? Beachten Sie dazu die Zahl der gleichberechtigten Möglichkeiten und berechnen Sie dann die Entropie.

• Lösung: H = 5,17
• Lösungsweg: Siehe Entropie:_Loesungen

9b. Sie haben ein normales Kartenspiel mit 4 Farben und 13 Karten je Farbe (As, 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König). Das heißt es gibt 52 verschiedene Karten. Die Karten werden ausführlich gemischt. Wie groß ist die Entropie aller möglichen Kartenanordnungen beim Zug einer Karte nach der anderen? Beachten Sie dazu, daß die Zahl der gleichberechtigten Möglichkeiten sich bei jedem Zug um 1 reduziert.

• Lösung:H = 226 = ld 52! = binärer Logarithmus der Fakultät von 52
  • 52! = 52*51*50*49*48*.....*1
  • H = ld 52 + ld 51 + ld 50 + ld 49 ..... + ld1
  • Genauere Lösung H = 225,5810031237027702

Bei dieser Aufgabe erkennt man, wie praktisch die Angabe des Logarithmus anstatt der Gesamtzahl aller Möglichkeiten ist. Die meisten Rechner können eine Fakultät von 52 nicht mehr berechnen, so groß ist die Zahl.

• Lösungsweg: Siehe Entropie:_Loesungen

Entropie und Gene

Sie haben eine Gensequenz und versuchen die Entropie dieser Sequenz zu berechnen.

   1 gagcagcgcg cgcaagcagg ccaggggaag gtgggcgcag gtgaggggcc gaggtgtgcg
  61 caggacttta gccggttgag aaggatcaag caggcatttg gagcacaggt gtctagaaac

Fortsetzung siehe Entropie:_Biologie#Entropie_im_genetischen_Code

Links zu weiteren Übungsaufgaben

• http://www.tf.uni-kiel.de/matwis/amat/mw1_ge/kap_5/exercise/e5_3_1.html
  • einfache Übungsaufgaben in Kombinatorik

Die Entropie beliebiger binärer Folgen

Will man die Entropie verstehen, kann man sich mit den einfachsten Informationsfolgen beschäftigen in denen der Unterschied zwischen hoher und niedriger Entropie schon auf den ersten Blick erkennbar ist. Man nimmt dazu binäre Zahlenfolgen von Null und Eins und versucht eine Aussage zur Entropie zu treffen.

 Chaitin hat dazu ein einfaches Beispiel angegeben:

Was ist der Unterschied zwischen

10101010101010101010 

und

01101100110111100010

wenn man die Folgen vom Standpunkt Entropie und Ordnung her betrachtet.

Siehe auch

• http://www.cs.auckland.ac.nz/CDMTCS/chaitin/index.html bzw *http://www.cs.auckland.ac.nz/CDMTCS/chaitin/sciamer.html und
  • chaitin G.J. 1975 scientific American 232 S 47 -52

Die erste Sequenz ist hochgeordnet und kann leicht komprimiert werden: zehnmal "10" Die zweite Sequenz ist eine Zufallsfolge, die durch 20 maliges Werfen einer Münze gewonnen wurde. Das ist der Unterschied. Deswegen ist auch die Entropie in der ersten Folge niedrig und nahe Null. Die Entropie der zweiten Folge ist hoch.

Wie kann man nun die Entropie dieser beiden 01 Sequenzen berechnen.

Dazu kann man sich eines statistischen Testes auf Zufälligkeit, des sogenannten  Runtests, bedienen.

Chaitins Binärzahlen, Berechnung der Zufälligkeit mit dem Runstest, Javascript Programm

Erklärung des Programmes

• pz wird von einer 20 stelligen binären Beispielzahl berechnet
• 01101100110111100010 = in diesem Fall Chaitinszahl Nr2
• 11 = zahl der runs in t
  • Das kann man leicht selber nachzählen

01101100110111100010 
1 23 4 5 67   8  9AB runs
                  A = 10 B = 11 runs

• s = zahl der stellen 20,
  • davon 11 mal die Eins und 9 mal die Null
  • Das kann man leicht selber nachzählen
• um = 11
  • Zwischenwert bei der Berechnung von pz
• varianz = 4.7368421052631575
  • Zwischenwert bei der Berechnung von pz
• pz = 0
  • Prüfziffer der Zufälligkeit,
  • ein pz um den Wert 0 bedeutet: hohe Zufälligkeit.

Programmlisting

<html>
<meta charset="utf-8">
< h2>
Die Pruefziffer pz des Runstestes wird von einer 20 stelligen Beispielzahl berechnet
< br>
<script>
let t = "01101100110111100010";
//binäre Zahl mit 20 Stellen 
let s = t.length;
document.write(t);document.write("< br>");
runz = 0;
for (n=0;n<s-1;n++) 
{ if (`${t.at(n)}` != `${t.at(n+1)}`) {runz=runz+1;}}
//eigentlich werden nur die 01 bzw 10 wechsel gezaehlt
runz = runz + 1;
//runz = wechsel + 1
document.write(runz + " = zahl der runs in t");
document.write("
");
um = 2 * s/2 * s/2 /( s/2 + s/2 ) + 1;
document.write("s = zahl der stellen " + s);
document.write("< br>");
document.write(" um = " + um);
document.write("< br>");
zw = 2 * s/2 * s/2;
varianz = zw *( zw - s) / (s * s * (s - 1));
if (varianz < 0) {varianz = -varianz}
document.write(" varianz = " + varianz);
document.write("< br>");
svar = varianz**0.5;
//Wurzel aus der Varianz
pz = (runz - um)/svar;
document.write(" pz = " + pz);
document.write("< br>");
</script>
< /h2>
</html>

Wenn man das Programm mit der zweiten Chaitinzahl durchlaufen läßt schaut die Sache ganz anders aus:

pz wird von einer 20 stelligen Beispielzahl berechnet

• Binärzahl 10101010101010101010 Chaitin Nr2
• 20 = zahl der runs
• s = zahl der stellen 20
• um = 11, Zwischenwert der Prüfzifferberechnung
• varianz = 4.7368421052631575 Zwischenwert der Prüfzifferrechnung
• pz = 4.135214625627066
  • hoher Wert, d.h. die Sequenz ist nicht zufällig, sondern hoch geordnet
  • ein positiver Wert von pz zeigt eine wiederholende Ordnung an

Wenn sie das Programm auf ihrem Handy in Gang gebracht haben, dann können sie noch folgende Zahl testen: 10 mal 1 und 10 mal die 0 . d.h. 20 Stellen, nur 2 Runs

pz wird von einer 20 stelligen Beispielzahl berechnet

• 10 mal die Eins, dann 10 mal die Null
  • ( Wikipedia mag übrigens solche hochgeordneten Zahlen nicht, wenn man sie anonym eingibt.)
  • Sie wird als unsinnige Zeichenfolge bezeichnet.

• 2 = zahl der runs in t
• s = zahl der stellen 20
• um = 11
• varianz = 4.7368421052631575
• pz = -4.135214625627066
  • hoher pz Wert heißt: hochgeordnete Folge ,
    • negativer pz Wert heißt symmetrisch geordnet

Programmierung des Runtestes in Basic/Gambas

Hier findet sich ein Programm für den Runtest.

• http://de.wikibooks.org/wiki/Gambas:_Statistik#Runtest

Leider funktioniert der Runtest nicht bei beliebigen 01 Sequenzen , sondern nur wenn die Zahl von 0 und 1 ungefähr gleich ist. Beispielsweise kann man eine Sequenz 00000000000000000010 im Runtest nicht auf ihre Zufälligkeit überprüfen.

Beispiellisting einer Entropieberechnung mit dem Runtestes für eine 01 Folge fester Länge

Programmiersprache Gambas

• Die Länge der 01 Folge ist variierbar , hier s = 8. ( Länge ist die Variable s im Listing)
• Die Zahl der Nullen und Einsen ist zur Vereinfachung gleich groß.
• Das Programm startet von alleine.
• Die Ergebnisausgabe erfolgt im Direkfenster.
• Bewertung:
  • pz Werte um die 0 sind ein Zeichen hoher Entropie. Pz-Werte über 1,5 oder unter -1,5 sind ein Zeichen niedriger Entropie

PUBLIC SUB Form_Open()
s AS Integer
'Laenge der Binaerzahl
z AS Integer
'Zaehler von 0 bis 2^s-1
zz AS Integer 
'Zaehler von 1 bis alle Varianten mit ozaehler = izaehler
t AS String
'binaerzahl
ozaehler AS Integer
'Zahl der Nullen
izaehler AS Integer
'Zahl der Einser
tt AS String 
'binaerzahl als String
n AS Integer 
'Laenge der Binaerzahl
char AS String 
UM AS Float 
varianz AS Float
svar AS Float
'Quadratwurzel der Varianz
zwei AS Integer 
summe AS Integer 
run AS Integer 
nn AS Integer
chari AS String
charnext AS String 
runzaehler AS Integer
pz AS Float 
'Pruefvariable entspricht dem Entropiewert der Folge
'pz Werte um die 0 sind ein Zeichen hoher Entropie. 
'Pz-Werte über 1,5 oder unter -1,5 sind ein Zeichen niedriger Entropie 
s = 10
'Laenge der 01 Folge
zz = 0
FOR z = 0 TO (2^s - 1)
 t = Bin$(z,s)
 tt = Str(t)
 'PRINT "tt = " & tt
 ozaehler = 0
 izaehler = 0
 FOR n = 1 TO Len(tt)
       char = Mid$(tt, n, 1)
          SELECT CASE TRUE
          CASE char = "0"
           ozaehler = ozaehler + 1
          CASE char = "1"
           izaehler = izaehler + 1
       END SELECT
 NEXT  
 'PRINT izaehler
 'PRINT ozaehler 
 IF izaehler = ozaehler THEN 
 zz = zz + 1
 t = tt 
 PRINT "zz = " & zz & " t = " &  t;
 'runtest
 UM = 2 * s/2 * s/2 /( s/2 + s/2 ) + 1
 'PRINT "UM  = " & UM 
 zwei = 2 * s/2 * s/2
 summe = s 
 varianz = zwei *( zwei - summe) / (summe * summe * (summe - 1))
IF varianz < 0 THEN varianz = -varianz 
'PRINT "Varianz = " & varianz
runzaehler = 1
   FOR nn = 1 TO Len(t) - 1
           chari = Mid$(t, nn, 1)
       charnext = Mid$(t, nn + 1, 1)
       IF chari <> charnext THEN runzaehler = runzaehler + 1
  NEXT
'PRINT " runzaehler = " & runzaehler;
svar = Sqr(varianz)
pz = ( runzaehler - UM)/svar 
PRINT " pz = " & Str(pz)
'PRINT Str(pz)
ENDIF
NEXT 
END

Ergebnisausgabe:

zz = 1 t = 00001111 pz = -2,291287847478
zz = 2 t = 00010111 pz = -0,763762615826
zz = 3 t = 00011011 pz = -0,763762615826
zz = 4 t = 00011101 pz = -0,763762615826
zz = 5 t = 00011110 pz = -1,527525231652
zz = 6 t = 00100111 pz = -0,763762615826
zz = 7 t = 00101011 pz = 0,763762615826
zz = 8 t = 00101101 pz = 0,763762615826
zz = 9 t = 00101110 pz = 0
zz = 10 t = 00110011 pz = -0,763762615826
zz = 11 t = 00110101 pz = 0,763762615826
zz = 12 t = 00110110 pz = 0
zz = 13 t = 00111001 pz = -0,763762615826
zz = 14 t = 00111010 pz = 0
zz = 15 t = 00111100 pz = -1,527525231652
zz = 16 t = 01000111 pz = -0,763762615826
zz = 17 t = 01001011 pz = 0,763762615826
zz = 18 t = 01001101 pz = 0,763762615826
zz = 19 t = 01001110 pz = 0
zz = 20 t = 01010011 pz = 0,763762615826
zz = 21 t = 01010101 pz = 2,291287847478
zz = 22 t = 01010110 pz = 1,527525231652
zz = 23 t = 01011001 pz = 0,763762615826
zz = 24 t = 01011010 pz = 1,527525231652
zz = 25 t = 01011100 pz = 0
zz = 26 t = 01100011 pz = -0,763762615826
zz = 27 t = 01100101 pz = 0,763762615826
zz = 28 t = 01100110 pz = 0
zz = 29 t = 01101001 pz = 0,763762615826
zz = 30 t = 01101010 pz = 1,527525231652
zz = 31 t = 01101100 pz = 0
zz = 32 t = 01110001 pz = -0,763762615826
zz = 33 t = 01110010 pz = 0
zz = 34 t = 01110100 pz = 0
zz = 35 t = 01111000 pz = -1,527525231652
zz = 36 t = 10000111 pz = -1,527525231652
zz = 37 t = 10001011 pz = 0
zz = 38 t = 10001101 pz = 0
zz = 39 t = 10001110 pz = -0,763762615826
zz = 40 t = 10010011 pz = 0
zz = 41 t = 10010101 pz = 1,527525231652
zz = 42 t = 10010110 pz = 0,763762615826
zz = 43 t = 10011001 pz = 0
zz = 44 t = 10011010 pz = 0,763762615826
zz = 45 t = 10011100 pz = -0,763762615826
zz = 46 t = 10100011 pz = 0
zz = 47 t = 10100101 pz = 1,527525231652
zz = 48 t = 10100110 pz = 0,763762615826
zz = 49 t = 10101001 pz = 1,527525231652
zz = 50 t = 10101010 pz = 2,291287847478
zz = 51 t = 10101100 pz = 0,763762615826
zz = 52 t = 10110001 pz = 0
zz = 53 t = 10110010 pz = 0,763762615826
zz = 54 t = 10110100 pz = 0,763762615826
zz = 55 t = 10111000 pz = -0,763762615826
zz = 56 t = 11000011 pz = -1,527525231652
zz = 57 t = 11000101 pz = 0
zz = 58 t = 11000110 pz = -0,763762615826
zz = 59 t = 11001001 pz = 0
zz = 60 t = 11001010 pz = 0,763762615826
zz = 61 t = 11001100 pz = -0,763762615826
zz = 62 t = 11010001 pz = 0
zz = 63 t = 11010010 pz = 0,763762615826
zz = 64 t = 11010100 pz = 0,763762615826
zz = 65 t = 11011000 pz = -0,763762615826
zz = 66 t = 11100001 pz = -1,527525231652
zz = 67 t = 11100010 pz = -0,763762615826
zz = 68 t = 11100100 pz = -0,763762615826
zz = 69 t = 11101000 pz = -0,763762615826
zz = 70 t = 11110000 pz = -2,291287847478

Grafische Darstellung der Entropiewerte einer 8er 01 Folge

Skizze einer berechneten Ordnungs-Entropielandschaft von 01 Folgen

Entropie beliebiger 01 Folgen

Will man den Entropiewert einer beliebigen 01 Folge berechnen, bei der sich die Zahl der Nullen und Einsen deutlich unterscheidet, kann man folgenden Trick benutzen: Man ordnet jeder Ziffer der ursprünglichen 01 Folge eine doppelt solange Binärzahl nach folgendem Schema zu: Aus einer 0 wird eine 01 und aus einer 1 wird eine 10. Beispiel:

000000 > 010101010101
010010 > 011001011001
111111 > 101010101010

Die resultierende Binärzahl ist doppelt solang, ist eindeutig der ursprünglichen Zahl zu zuordnen und kann problemlos mit dem Runtest bearbeitet werden. Aus der berechneten pz Zahl kann man dann die Entropie der ursprünglichen Zahl zurückrechnen, wenn man der größten bzw negativen kleinsten Zahl die Entropie 0 zuordnet. Eine pz Zahl von 0 bedeutet eine maximale Entropie die der Länge der ursprünglichen Binärzahl entspricht. Alle pz Zahlen dazwischen werden einfach proportional umgerechnet. Die proportionale Umrechnung ist willkürlich gewählt, kann man aber als erste Näherung sicher zunächst gelten lassen. So kann man dann jeder beliebigen Binärzahl einen Entropiewert zuordnen. Das ganze kann als Ergänzung zu obigem Basic Programm einfach wiederum als Computerprogramm umgesetzt werden. Man gibt dann eine beliebige 01 Folge ein und der PC berechnet die zugehörige Entropie.

Bei dieser Methode geht allerdings auch Information verloren, denn aus 00001111 wird beispielsweise 0101010110101010. Aus der zunächst symmetrischen Ordnung wird eher eine wiederholende Ordnung mit einem umgekehrten Vorzeichen der pz Zahl.

Sehr schnell merkt man auch, daß die Berechnung aus praktischen Gründen auf eine gewiße Länge der Binärzahl begrenzt bleibt, da sonst der PC zu lange rechnet.

Außerdem ist eine gewisse Eichung sinnvoll. Eine hochgeordnete Folge die nur aus Nullen bzw nur aus Einsern besteht erhält per Definition die Entropie Null und die reine Zufallsfolge mit einem pz unterhalb einer Grenze mit einer festzulegenden Irrtumswahrscheinlichkeit p ( beispielsweise p < 0,05 ) erhält die maximal mögliche Entropie, die der Länge der Binärzahl entspricht.

Entropie und Sprache

Wahrscheinlichkeit und Entropie einzelner Buchstaben der englischen Sprache

Nr Buchstabe  Wahrscheinlichkeit     Entropie
1  a          .0575                   4.1
2  b          .0128                   6.3
3  c          .0263                   5.2
4  d          .0285                   5.1
5  e          .0913                   3.5
6  f          .0173                   5.9
7  g          .0133                   6.2
8  h          .0313                   5.0
9  i          .0599                   4.1
10 j          .0006                  10.7
11 k          .0084                   6.9
12 l          .0335                   4.9
13 m          .0235                   5.4
14 n          .0596                   4.1
15 o          .0689                   3.9
16 p          .0192                   5.7
17 q          .0008                  10.3
18 r          .0508                   4.3
19 s          .0567                   4.1
20 t          .0706                   3.8
21 u          .0334                   4.9
22 v          .0069                   7.2
23 w          .0119                   6.4
24 x          .0073                   7.1
25 y          .0164                   5.9
26 z          .0007                  10.4
27 -          .1928                   2.4

Entropietexte übernommen aus Wikipedia

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 $p_{j}$ erreicht wird, zur Normierung heranzuziehen. Sei $z=|Z|$ die Anzahl der erlaubten Symbole in $I$ über dem Alphabet $Z$, dann ist die maximale Entropie $H_{\text{max}}$ gegeben durch:

$H_{\text{max}}(I)=-\sum _{i}{{\frac {1}{z}}\log _{2}{\frac {1}{z}}}=\log _{2}{z}{\text{ , falls }}\forall \;p_{j}={\frac {1}{|Z|}}$

Daraus folgt beispielsweise $H_{\text{max}}=1$ für eine Binärverteilung ($Z=\{0,1\}$), also benötigt man 1 Bit pro Zeichen und $|I|$ Zeichen für die komplette Information $I$. Dieser Wert wird erreicht, wenn 0en und 1en gleich häufig vorkommen. Normiert man nun die Entropie einer beliebigen Verteilung mit $z$ verschiedenen Symbolen mit $H_{\text{max}}$ erhält man:

${\frac {H(I)}{H_{\text{max}}}}=-\sum _{j=1}^{b}{p_{j}\cdot {\frac {\log _{2}{p_{j}}}{\log _{2}{b}}}}=-\sum {p_{j}\cdot \log _{b}{p_{j}}}\leq 1$

Die so erhaltene Entropie wird immer maximal gleich 1.

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.

Entropietests

Um zu testen, wie gut Daten komprimierbar sind, oder um Zufallszahlen zu testen, werden Entropietests verwendet. Als Zufallszahltest wird die Entropie einer bestimmen 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 sein.

Einfaches Beispiel: Eine Quelle, z. B. ein Spielwürfel oder eine Münze, gibt nur 0xaa (dezimal 170) und 0x55 (dezimal 85) aus und beide mit gleicher Wahrscheinlichkeit. Bitweise ist der output zu 50 % 0 oder 1, byteweise ist er zu 50 % 0xaa oder 0xff. Die bitweise Entropie ist (mit log = ln): H = 1/log(2) *(1/2 *log(1/2) +1/2 *log(1/2)) = 1 während die byteweise Entropie mit H = 1/log(8) *(1/2 *log(1/2) +1/2 *log(1/2)) = 1/3 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 Bytes verwendet werden, aber wenn auch die anderen Bytes mit einer kleinen Wahrscheinlichkeit von z. B. 1/123456789-tel ausgegeben, 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-tel erreicht die byteweise Entropie den Wert 1, aber dann kann es noch Korrelationen der Bytes geben, also z. B. 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 Markov-Kette. Allerdings ist der Rechenaufwand dafür bei realen Zufallszahlengeneratoren sehr hoch.

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ße für die durch eine schlechte Kodierung ausgelösten Verschwendungen von Bits eine Rolle.

Beispiel: Entropiekodierung

• Gegeben sei die Zeichenkette ABBCAADA.
• Die Buchstaben-Wahrscheinlichkeit: $p_{A}=4/8=0{,}5$; $p_{B}=0{,}25$; $p_{C}=p_{D}=0{,}125$
  $Entropie=-(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\ {\frac {\mbox{Bit}}{\mbox{Zeichen}}}$
• Maximalentropie ($p_{A}=p_{B}=p_{C}=p_{D}=0{,}25$):
  $Entropie_{max}=-4\cdot (0{,}25\cdot \log _{2}{0{,}25})=-\log _{2}{4^{-1}}=\log _{2}{4}=2\ {\frac {\mbox{Bit}}{\mbox{Zeichen}}}$

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 Laufzeit bzw. Zeitkomplexität eines Algorithmus zur Erzeugung der Daten bezieht.

Literatur

• Johanneson, Rolf: Informationstheorie, Addison-Wesley 1992, ISBN 3893194657
• Claude Shannon und Warren Weaver: The Mathematical Theory of Communication, University of Illinois Press 1963, ISBN 0252725484 (Softcover) und ISBN 0252725468 (Hardcover)
• Norbert Bischof: Struktur und Bedeutung, 1998, ISBN 3456830807 (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.)

Weitere Begriffe

• Kolmogorov-Entropie, Kolmogorov-Sinai-Entropie, Maximum-Entropie-Methode, Metrische Entropie, Nat, Ornstein Theorem, Redundanz, Topologische Entropie, Markow-Kette, Renyi-Entropie, Tsallis-Entropie, Theil-Entropie, Negentropie, Entropiekodierung

Weblinks

• http://www.madeasy.de/2/zufallgz.htm
  • nur noch im Webarchiv aufrufbar
    • https://web.archive.org/web/20171106170359/http://www.madeasy.de/
  • Einführung der Entropie als quantitatives Maß für den Zufall mit vielen Beispielen und hilfreichen Erklärungen zur Formel von Shannon.

• http://www.techfak.uni-kiel.de/matwis/amat/mw1_ge/kap_5/advanced/t5_3_2.html
  • Entropie und Information, gut erklärt