Zufall: Mathematik

Zurück zur Übersicht

 Pierre-Simon Laplace beschäftigte sich eingehend mit dem Zufall

Zufall in der Mathematik

Einleitung

Die  Stochastik ist die Teildisziplin der Mathematik, die sich mit dem Zufall beschäftigt. Etwas plakativ hat man die Statistik früher als die Physik der Mathematik bezeichnet und oft als vermeintlich unexakt eingeschätzt. Diese Einstellung hat sich mittlerweile weitgehend geändert. Zur rein deskriptiven Statistik ist die bewertende  Statistik und die Wahrscheinlichkeitstheorie hinzugekommen. Statistik und Wahrscheinlichkeitstheorie hat man dann unter dem neuen Begriff der Stochastik zusammengefasst.

Die Mathematik setzt eine Vorstellung vom Zufall voraus und liefert Rechenmodelle, mit denen sich zufällige Ereignisse quantifizieren lassen. Eine grundlegende Klärung, was denn Zufall eigentlich ist, will die Mathematik bisher nicht liefern. Trotzdem war das Experimentieren und das Rechnen mit dem Zufall sehr fruchtbar. Ohne sich in Grundsatzdiskussionen zu verstricken, wurden wichtige Erkenntnisse über den Zufall gewonnen, die die Philosophie nicht liefern konnte.

Stochastik ist der Oberbegriff für 
    die Statistik und 
    die Wahrscheinlichkeitstheorie

Zufallsexperiment

In der  Wahrscheinlichkeitstheorie bezeichnet man ein Experiment, das, wenn es unter gleichen Bedingungen wiederholt wird, nicht notwendigerweise das gleiche Ergebnis liefert, als ein Zufallsexperiment. Als Experiment versteht man hier einen Vorgang, der ein nicht vorhersagbares, erfassbares Ergebnis zur Folge hat, zum Beispiel das Werfen einer Münze oder eines Spielwürfels.

Obwohl das Ergebnis jedes einzelnen Versuchs zufällig ist, lassen sich bei hinreichend häufiger Wiederholung Gesetzmäßigkeiten erkennen. Die interessierenden Größen eines Zufallsexperimentes nennt man Zufallsvariablen.

Beispiel eines Zufallsexperimentes

Die Stufen eines Zufallsexperiments sind folgende:

1. Vor dem Experiment: Mindestens 2 Ergebnisse sind möglich, es ist aber noch nichts entschieden.
2. Das Zufallsexperiment wird durchgeführt.
3. Aus den mindestens 2 möglichen Ergebnissen wurde eines zufällig ausgewählt.

Das einfachste Zufallsexperiment hat zwei mögliche Ergebnisse, die die gleiche Wahrscheinlichkeit besitzen.

Man kann mit einer Münze diese Art von Zufallsexperiment durchführen und selber Zufallszahlen erzeugen. Dabei ordnet man der einen Seite der Münze die Zahl 0, der anderen die Zahl 1 zu. Durch Notieren vieler Wurfergebnisse erhält man eine Folge von 0 und 1. Eine solche Folge ist das Ergebnis eines sehr einfachen Zufallsprozesses.

Die so erhaltenen Zufallsfolgen von 0 und 1 sind leicht statistisch untersuchbar. Dabei kann man Eigenschaften dieser Zufallsfolgen feststellen, die bei nicht-zufälligen Folgen (also Folgen, die deterministisch nach irgendeinem Gesetz erzeugt wurden) nicht auftreten. Auf diese Weise kann man Zahlenfolgen auf echte Zufälligkeit prüfen.

Auffällige statistische Abweichungen von reinen Zufallsfolgen können zum Beispiel verwendet werden, um wissenschaftliche Fälschungen zu enttarnen, da Messungen stets auch einen zufälligen Messfehler beinhalten, während erfundene Zufallsfehler oft gerade durch den Versuch, sie möglichst zufällig erscheinen zu lassen, deutliche Abweichungen vom Zufallsergebnis enthalten.

Je länger eine Zahlenfolge ist, desto klarer kann unterschieden werden, ob es sich um eine zufällige oder nicht zufällige Folge handelt. Theoretisch kann auch ein Zufallsexperiment eine Folge von hundert Nullen hintereinander liefern, nur ist das so unwahrscheinlich, dass man in diesem Fall mit gutem Recht von einer Regelmäßigkeit ausgehen darf. Auf der anderen Seite gibt es deterministische Algorithmen, deren Ergebnisse sehr ähnlich denen eines Zufallsexperiments sind, so genannte Pseudozufallsgeneratoren. Bei guten Pseudozufallsgeneratoren braucht man eine sehr lange Zahlenreihe, um den Unterschied zum echten Zufall erkennen zu können. In der Informatik werden gelegentlich Zufallszahlen benötigt. Der Versuch, sie mit dem Computer zu berechnen, ist möglich, allerdings immer nur für kürzere Sequenzen wirklich überzeugend. Bei längeren Sequenzen kommt irgendwann die Nichtzufälligkeit zu Tage.

Eine 01 Folge, die die Realität abbildet, ist nicht immer rein deterministisch oder rein zufällig, sondern es liegt häufig eine Mischung aus beidem vor. Ein einfaches Beispiel wäre, wenn man beispielsweise stets eine Ziffer per Münzwurf bestimmt, die nächste als den Unterschied zwischen den beiden vorhergehenden Ziffern, dann wieder Münzwurf, und so fort. Durch Untersuchung solcher Folgen bekommt man ein recht gutes Verständnis für den Zufall und die Mischung von Zufälligem und Nichtzufälligem, wie es ja oft in der Realität anzutreffen ist.

Ein elementares Zufallsereignis beruht auf Gleichheit und Ungleichheit

• Die zwei möglichen Varianten müssen gleich sein (das heißt gleichwahrscheinlich).
• Trotzdem müssen sie irgendwie ungleich, nämlich unterscheidbar sein.

(Münze: beide Seiten müssen mit derselben Wahrscheinlichkeit auftreten können, trotzdem müssen beide Seiten verschieden geprägt (beziehungsweise gefärbt etc.) sein, sonst könnte man sie nicht unterscheiden.)

Basisbegriffe beim mathematischen Zufall

Bei einem zufälligen Ereignis, welches mathematisch betrachtet und bewertet werden soll, muss man drei Begriffe trennen:

• Zahl der Möglichkeiten
  • welche und wieviele alternative Ergebnisse gibt es
  • man nennt das auch Ereignisraum eines zufälligen Ereignisses
• Wahrscheinlichkeit
  • wie wahrscheinlich ist jedes Ergebnis
• Menge an Zufallsinformation = Entropie in der Mathematik
  • Wieviel Zufall d. h. Entropie steckt in dem Ereignis

Um das zu verstehen, betrachtet man am besten ein einfaches Beispiel:

Für den idealen einmaligen Münzwurf gilt:

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

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

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

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

Zufall quantitativ

In der formalen Welt der Mathematik lassen sich abstrakte Strukturen definieren, die aus der menschlichen Vorstellung beziehungsweise Erwartung von Zufall motiviert sind. Glücksspiele motivierten die ersten mathematischen Wahrscheinlichkeitstheorien und werden auch heute noch oft zu ihrer Illustration eingesetzt.

Die folgenden Begriffe sind zentral zur formalen Beschreibung des Zufalls:

(Zufalls)experiment: Die durchgeführten und/oder beobachteten Vorgänge (beispielsweise zweimaliges Werfen eines Würfels).

Ergebnis oder Elementar-Ereignis: Beobachtung (beispielsweise erster Wurf '3', zweiter Wurf '5').

Ereignis: Aus Elementarereignissen zusammengesetze Menge (das Ereignis "gerade Zahl gewürfelt" ist aus den Elementarereignissen "2,4 oder 6 gewürfelt" zusammengesetzt).

Wahrscheinlichkeit: Jedem Elementarereignis wird ein Zahlenwert zwischen 0 (tritt nie ein) und 1 (tritt immer ein) zugeordnet (beispielsweise Gleichverteilung: Die Wahrscheinlichkeit für jede Zahl auf dem Würfel ist gleichgroß, nämlich 1/6). Bei einem Kontinuum möglicher Ergebnisse spricht man von einer Wahrscheinlichkeitsverteilung.

Offensichtlich sind nur solche Zufallsexperimente interessant, die mehr als ein mögliches Ergebnis haben.

Die Statistik versucht, zu einem gegebenen Zufallsexperiment die zugrundeliegende Wahrscheinlichkeitsverteilung zu ermitteln.

Zufallsvariable, Zufallsgröße

Als Zufallsvariable oder Zufallsgröße bezeichnet man eine mathematische Variable, die je nach dem Ergebnis einer als zufällig aufgefassten Prozedur verschiedene Werte annehmen kann. Die Prozedur kann eine Auslosung sein, die Berechnung einer Pseudozufallszahl oder die Messung einer statistisch verteilten und/oder mit Messfehler behafteten Größe.

Beispielsweise ist die Augenzahl eines Würfels eine Zufallsvariable, die die Werte 1, 2, 3, 4, 5 oder 6 annehmen kann.

Wenn die Menge der möglichen Werte einer Zufallsvariablen endlich (wie beim Würfel) oder abzählbar unendlich ist, nennt man die Zufallsvariable diskret. Wenn die Wertemenge überabzählbar ist, typischerweise also aus reellen Zahlen besteht (wie bei der idealisierten Messung einer physikalischen Größe), heißt die Zufallsvariable stetig (kontinuierlich).

Die Wahrscheinlichkeiten der möglichen Werte einer diskreten Zufallsvariable bilden eine Wahrscheinlichkeitsverteilung.

Die Wahrscheinlichkeit, beim Würfeln mit zwei Würfeln die Gesamtaugenzahl Z zu erreichen, folgt zum Beispiel der Wahrscheinlichkeitsverteilung

$P(Z)={\frac {(6-|7-Z|)}{36}}$.

Den möglichen Wert einer kontinuierlichen Zufallsvariablen kann man dagegen keine endliche Wahrscheinlichkeit zuordnen; man muss hier mit Wahrscheinlichkeitsdichten und/oder kumulativen Wahrscheinlichkeitsverteilungen arbeiten.

In einer abstrakteren Formulierung der Wahrscheinlichkeitstheorie bezeichnet man als Zufallsvariable eine messbare Funktion von einem Wahrscheinlichkeitsraum in einen Maßraum. Normalerweise wählt man als Bildraum die Menge der |reellen Zahlen, ausgestattet mit der Borelschen σ-Algebra.

Zufallszahlen

In der Statistik bezeichnet man mit Zufallszahl den Wert einer Zufallsvariable bei einem Zufallsexperiment. Das Ergebnis des Experiments ist von früheren Ergebnissen unabhängig.

Zufallszahlen werden bei verschiedenen Methoden der Statistik benötigt, z. B. bei der Auswahl einer repräsentativen Stichprobe aus einer Grundgesamtheit, bei der Verteilung von Versuchstieren auf verschiedene Versuchsgruppen (Randomisierung), bei der Monte-Carlo-Simulation u. a.

Zur Erzeugung von Zufallszahlen gibt es verschiedene Verfahren. Echte Zufallszahlen werden mit Hilfe physikalischer Phänomene erzeugt: Münzwurf, Würfel, Roulette, Rauschen (Physik) elektronischer Bauelemente, radioaktive Zerfallsprozesse. Diese Verfahren sind jedoch recht zeitaufwändig. In der realen Anwendung genügt meist eine Folge von Pseudozufallszahlen, d. h. scheinbar zufällige Zahlen, die nach einem festen, reproduzierbaren Verfahren erzeugt werden. Sie sind also nicht wirklich zufällig, haben aber ähnliche statistische Eigenschaften (gleichmäßige Häufigkeitsverteilung, geringe Korrelation) wie echte Zufallszahlenfolgen.

Siehe auch http://de.wikipedia.org/wiki/Verteilung_von_Zufallszahlen

Programmierung des Zufalls in Javascript

Jede Programmiersprache hat ihre eigenen Methoden und Befehle, um den Zufall in das Programmgeschehen einzubinden. Das Interessante an der Programmierung ist dann, daß man durch häufige Wiederholungen, die Zufälligkeit des (Pseudo)Zufallsallgorithmus der jeweiligen Programmiersprache überprüfen kann. In der Regel liefern die meisten Programmiersprachen recht brauchbare Zufallszahlen. Meist werden in der einfachsten Befehlsversion typische Zufallszahlen in Form von Dezimalbrüchen zwischen 0 und 1 ausgegeben. zb 0,5462974166

Programmierung des Zufalls in Basic siehe Gambas:_Zufall

Zufallszahlen zwischen Null und Eins in Javascript

Im Folgenden ist ein simples Javascriptprogramm aufgelistet, welches 3 Zufallszahlen zwischen 0 und 1 liefert.

<html>
test-Zufallszahlen 3 mal 
<script>
var e = Math.random()
document.write(e);
var f = Math.random()
document.write(f);
var g = Math.random()
document.write(g);
</script>
</html>

Münzwurf

Im Folgenden ist ein simples Javascriptprogramm aufgelistet, welches 3 Münzwürfe simuliert und eine zufällige Folge von 0 und 1 liefert.

<html>
test-muenzwurf 3 mal 
<script>
var e = Math.floor(Math.random()*2)
document.write(e);
var f = Math.floor(Math.random()*2)
document.write(f);
var g = Math.floor(Math.random()*2)
document.write(g);
</script>
</html>

Der Wuerfel ( Der 6er Würfel )

Folgendes html/js Programm simuliert den Wurf eines 6er Würfels. Es kommt immer eine ganze Zahl zwischen 1 und 6 heraus.

<html> 
<body> 
<print>Das Programm simuliert genau einen Wuerfelwurf. ----- </print>
<script>
 let ww = 1;
 //ww ist eine Zahlenvariable und soll fuer den wuerfelwurf stehen. 
 //ww kann ganze Zahlen von 1 bis 6 annehmen
 ww=Math.floor(Math.random() * 6) + 1;    
 document.write("Der Wuerfelwurf hat eine " + ww + " ergeben. "); 
</script> 
</body> 
</html>

Pseudozufallszahlen

Der Affe an der Schreibmaschine, ein berühmter Zufallsgenerator

Als Pseudozufallszahlen bezeichnet man Zahlenfolgen, die durch einen deterministischen Algorithmus (Pseudozufallszahlengenerator) berechnet werden (und somit nicht zufällig sind), aber (für hinreichend kurze Sequenzen) zufällig aussehen. Bei jedem Start der Zufallszahlenberechnung mit gleichem Startwert wird die gleiche Zahlenfolge erzeugt (weswegen diese Zahlen weit davon entfernt sind, wirklich zufällig zu sein). Pseudozufallszahlen erzeugt man mit Pseudozufallszahlengeneratoren.

Die Zufälligkeit wird durch statistische Eigenschaften der Zahlenfolge bestimmt, wie Gleichwahrscheinlichkeit der einzelnen Zahlen und statistische Unabhängigkeit verschiedener Zahlen der Folge. Wie gut diese statistischen Forderungen erfüllt sind, bestimmt die Güte eines Pseudozufallszahlengenerators.

Eine Folge von Pseudozufallszahlen wird mittels deterministischer Algorithmen ausgehend von einem echt zufällig gewählten Startwert berechnet. Ein solcher Startwert kann z. B. die Systemzeit des Computers in Millisekunden im Moment des letzten Einschaltens sein. Diese Folge besitzt die Eigenschaft, dass es schwer ist, anhand einiger Zahlen die nächsten Zahlen der Folge vorherzusagen. Eine Folge von Pseudozufallszahlen "sieht zufällig aus".

Eigenschaften von Pseudozufallszahlalgorithmen

Einige Zufallszahlenalgorithmen sind periodisch. Auch wenn es meist besser wäre nicht-periodische Algorithmen zu verwenden, sind die periodischen oft deutlich schneller. Durch geschickte Wahl der Parameter kann man die Periode beliebig groß machen, weshalb sie in der Praxis den nicht-periodischen oft deutlich überlegen sind. Einige Pseudozufallszahlengeneratoren sind auch nur endlich, d. h. man kann mit ihnen nicht beliebig viele Zahlen erzeugen (von daher sind sie in gewissem Sinne verwandt mit den periodischen).

Drei Beispiele für Pseudozufallszahlengeneratoren

endlicher Generator

Um eine Folge von $N$ Zahlen zwischen $0$ und $m$ zu erzeugen, wähle man ein $k$ größer als $m^{2}$, ein $p$ größer als $(k+N)^{2}$ und nicht durch kleine Primzahlen teilbar (wobei klein hier bedeutet: kleiner als $m$).

$a_{n}=(p\mod (k+n))\mod m$

periodischer Generator

Man nehme Startzahlen $a_{0}$, $p$, $b$ und $m$, wobei $m$ die größte dieser Zahlen ist.

$a_{n}=(a_{n-1}p+b)\mod m$

Was ist $a_{n-1}$? Das ist die Zahl a, die man in die Formel eingibt, um den nächsten Wert für a zu berechnen . Man kann die Formel auch so schreiben: $a_{n+1}=(a_{n}p+b)\mod m$ und fängt dann mit $a_{0}$ zu rechnen an.

Ein weiteres Beispiel stellt der  Mersenne Twister dar.

nicht-periodischer/unendlicher Generator

Man nehme die Nachkommastellen einer Wurzel einer ganzen Zahl als Zufallszahlen

Verwendung von Pseudozufallszahlen

Pseudozufallszahlen werden u. a. in der Rechnersimulation angewandt, bei der statistische Prozesse mit Hilfe von Software simuliert werden. Pseudozufallszahlen können auch bei der Fehlersuche in Computerprogrammen nützlich sein. Andererseits macht diese Eigenschaft Pseudozufallszahlen für bestimmte Anwendungen unbrauchbar (so muss man beispielsweise in der Kryptographie aufpassen, dass man Pseudozufahlszahlen nicht an den falschen Stellen verwendet). Anwendung finden Pseudozufallszahlen auch in Rauschgeneratoren.

Ein weiterer Vorteil der Pseudozufallszahlen ist, dass sie auf jedem Rechner ohne Rückgriff auf externe Daten erzeugt werden können (was sie für bestimmte Bereiche der Kryptographie trotz oben genannter Nachteile wieder interessant macht). Zur Erzeugung echter Zufallszahlen braucht man entweder einen echten Zufallsgenerator (z. B. durch Digitalisieren von Rauschen oder durch Ausnutzen von Quanteneffekten) oder zumindest eine Quelle quasizufälliger (normalerweise nicht vorhersagbarer) Ereignisse wie Zeiten von Benutzereingaben oder Netzwerkaktivität.

Links zu Zufallsgeneratoren

• Siehe auch: http://www.swisseduc.ch/informatik/werkstatt/multiplik/zufgen/
• http://www.canb.auug.org.au/~dbell/programs/blumrand.tar.gz
  • blumrand – ein sehr guter Pseudozufallsgenerator

Das Gesetz der großen Zahl

Das Gesetz der großen Zahlen besagt, daß sich die relative Häufigkeit eines Zufallsergebnisses immer weiter an einen Mittelwert der Wahrscheinlichkeit für dieses Ergebnis annähert, je häufiger das Zufallsexperiment durchgeführt wird.

Gesetz der grossen Zahl als animierter Gif File

Beispiel: Münzwurf

Anzahl der Würfe  davon Kopf               Verhältnis Kopf/Gesamt             relativer Abstand
                  theoretisch beobachtet   theoretisch  beobachtet  
100               50          48           0,5          0,48                  0,02
1000              500         491          0,5          0,491                 0,009
10000             5000        4970         0,5          0,497                 0,0030

Das beobachtete Verhältnis Kopf/Gesamt (0,48 --> 0,491 --> 0,497 ) nähert sich bei steigender Anzahl der Würfe immer mehr dem theoretischen Verhältnis von 0,5 an.

Die Gaussche Normalverteilung

Die Normalverteilung

Bei der Messung einer physikalischen Größe zeigt sich oft eine charakteristische glockenförmige Verteilung der einzelnen Meßwerte um den Mittelwert. Um diese Glockenkurve zu erhalten, wiederholt man ein und dieselbe Messung sehr häufig und ordnet die erhaltenen Werte nach ihrer Häufigkeit in gleichbreite Spalten.

Erhält man dann so eine Glockenkurve kann man davon ausgehen, daß bei der Messung nur der Zufall für die Abweichung vom Mittelwert verantwortlich ist und die erhaltenen Meßergebnisse normalverteilt sind.

Für die Wahrscheinlichkeitsrechnung ist die Gaussche Glockenkurve eine der wichtigsten Verteilungen von Zufallsvariablen.

Um die Normalverteilung zu verstehen, sollte man ein wenig mit ihr experimentieren oder sie in einer einfachen Programmiersprache mit der Möglichkeit einer grafische Darstellung selbst programmieren. Da einen die griechischen Buchstaben in den Formeln vielleicht abschrecken, ersetzt man sie durch Buchstaben aus dem gewohnten lateinischen Alphabet.

Links

• http://www.gauss-goettingen.de/gauss_kniffelig_norm.php?navid=3&supnavid=7
  • Die Normalverteilung einfach und interaktiv erklärt
• https://web.archive.org/web/20160401023023/http://www.madeasy.de/2/gauss.htm
  • Programmcode in Visual Basic und Gambas zur grafischen Darstellung einer Normalverteilung.

Zufallsfolge – Zufallssequenz

Eine Zufallssequenz oder Zufallsfolge entsteht durch die wiederholte Anwendung eines statistischen Experiments. Eine Zufallssequenz ist im Allgemeinen eine Abfolge von Realisationen einer Zufallsvariablen. Der Begriff wird meistens im Sinne einer Abfolge von zufällig aus einem bestimmten Alphabet oder Zahlenvorrat ausgewählten Zeichen gebraucht.

Die einfachste Zufallssequenz gewinnt man durch einen wiederholten Münzwurf, wenn man einer Seite der Münze die 0 und der anderen die 1 zuordnet. Man kann andere Zufallssequenzen so in eine einfache 0-1-Sequenz umcodieren (dichotomisieren), ohne dass der Zufallscharakter verloren geht.

Beispiel: 1011011010101001110010110011100000011110010100001111010100010011011110110000100010 1010001110111001010111011111110000010011010000110111011110101011000001000111011000 1000000100111110000011111010010001101111001010100000101101000011000110100011001111 0111110001101110010011000000111110010000001100001000000110101010000011000101100001 1100111100100001101111111100100101010011111001000100100001001001000010001010011100 1111011000001010011111110010111110111011000111011010110000011101100111101011001110

Diese Folge wurde durch wiederholten Münzwurf gewonnen. Auffällig ist, wie oft längere zusammenhängende Sequenzen von 0 oder 1 zu finden sind.

 Alonzo Church bezeichnete eine Folge von Zahlen als zufällig, wenn sie nicht berechenbar ist oder wenn das kürzeste Computerprogramm, dass man zur Berechnung der Folge schreiben kann, länger ist als die Folge selbst.

Eine Zufallssequenz ist durch eine verschwindende serielle Korrelation oder auch Autokorrelation gekennzeichnet, d. h. der Korrelationskoeffizient zwischen aufeinander folgenden Werten in der Sequenz ist nicht signifikant von Null verschieden.

Viele natürlich vorkommenden zeit- bzw. ortsdiskreten Signale (z. B. DNA, siehe auch DNA-Sequenzanalyse) werden statistisch analysiert, indem man zunächst die Nullhypothese eines zugrunde liegenden Zufallsprozesses postuliert. Kann man diese Hypothese widerlegen, liegen also Korrelationen in der Sequenz vor, weisen diese unter Umständen auf in der Sequenz verborgene Nutzinformation hin. Speziell bei dichtomen Folgen kann man die Sequenzen mit Hilfe des Run-Tests auf Zufälligkeit überprüfen, wobei mit "Run" eine Folge gleicher Ausprägungen in der Sequenz bezeichnet wird. Der Test führt zur Ablehnung, wenn zu wenig, aber auch zu viel Runs in einer Sequenz sind.

Run-Test auf Zufälligkeit einer Sequenz

siehe auch  Run-Test

Der Run- oder Runs-Test (auch Wald-Wolfowitz-Test oder Iterationstest) ist ein nichtparametrischer Test auf Zufälligkeit einer Folge. Konzeptionell wird von einer zweigeteilten Grundgesamtheit, also beispielsweise einem Urnenmodell mit zwei Sorten Kugeln, ausgegangen. Es sind n viele Kugeln mit Zurücklegen entnommen worden. Es soll die Hypothese geprüft werden, daß die Entnahme zufällig erfolgt ist.

Vorgehensweise

Es wurden einer dichotomen Grundgesamtheit n Kugeln entnommen. Die Ergebnisse liegen in ihrer chronologischen Abfolge vor. Es werden nun alle benachbarten Ergebnisse gleicher Ausprägung zu einem Lauf oder Run zusammengefasst. Als deutsches Wort für den Begriff Run verwendet man am besten den Begriff Serie oder auch Serie von gleichen Ziehungen. Wenn die Folge tatsächlich zufällig ist, sollten nicht zu wenig Runs vorliegen, aber auch nicht zu viele.

Beispiel: Kugelfarbe Weiß dargestellt als eine Null und Kugelfarbe Schwarz dargestellt als eine Eins. Man zieht folgende Reihenfolge: 0011101110000010100110111010011000011100110010111001110111001010011110010101011000001111000000110111111001011011 0010110110011111100110111001011100011110001001011100000100010001001010101101110110111000

Der erste Run besteht dann aus zwei weißen Kugeln (00), dann folgt eine Serie von 3 schwarzen Kugeln (111), dann folgt eine einzelne weiße Kugel (0) etc.

Es wird die Hypothese aufgestellt: Die Entnahme erfolgte zufällig.

Für die Festlegung der Zahl der Runs, bei der die Hypothese abgelehnt wird, wird die Verteilung der Runs benötigt: Es seien n₁ die Zahl der Kugeln erster Sorte und n₂ = n - n₁ der zweiten Sorte; es sei r die Zahl der Runs. Nach dem Symmetrieprinzip ist die Wahrscheinlichkeit für jede beliebige Folge der Kugeln bei zufälliger Entnahme gleich groß. Es gibt insgesamt

${\frac {(n_{1}+n_{2})!}{n_{1}!\cdot n_{2}!}}$

Möglichkeiten der Entnahme.

Bezüglich der Verteilung der Zahl der Runs unterscheidet man die Fälle:

1. Die Zahl der Runs r ist geradzahlig:

   Es liegen $q={\frac {r}{2}}$ Runs der Kugeln der ersten Sorte und $p={\frac {r}{2}}$ Runs der Kugeln der zweiten Sorte vor. Die Wahrscheinlichkeit, dass genau r Runs eingetreten sind, ist dann

   $P(R=2q)={\frac {2{{n_{1}-1} \choose {q-1}}{{n_{2}-1} \choose {q-1}}}{{n_{1}+n_{2}} \choose n_{1}}}$

2. Die Zahl der Runs r ist ungeradzahlig:

   Es liegen $q={\frac {r-1}{2}}$ Runs der Kugeln der ersten Sorte und $p={\frac {r+1}{2}}$ Runs der Kugeln der zweiten Sorte vor oder der umgekehrte Fall. Die Wahrscheinlichkeit, dass genau r Runs eingetreten sind, berechnet sich dann als Summe aus diesen beiden Möglichkeiten

   $P(R=2q+1)={\frac {{n_{1}-1 \choose q}{n_{2}-1 \choose q-1}+{n_{1}-1 \choose q-1}{n_{2}-1 \choose q}}{n_{1}+n_{2} \choose n_{1}}}$

Ist r zu klein oder zu groß, führt das zur Ablehnung der Nullhypothese. Bei einem Signifikanzniveau von alpha wird H₀ abgelehnt, wenn für die Prüfgröße r gilt:

$r\leq r\left({\frac {\alpha }{2}}\right)$ oder $r\geq r\left(1-{\frac {\alpha }{2}}\right)$

mit r(p)als Quantil der Verteilung von R an der Stelle p, wobei hier das Prinzip des konservativen Testens angewendet wird. Da die Berechnung der kritischen Werte von r für die Ablehnung der Hypothese umständlich ist, bedient man sich häufig einer Tabelle.

Was bedeutet die Schreibweise ${n_{1}-1 \choose q}$?

Einfaches Beispiel

Für eine Podiumsdiskussion mit zwei politischen Parteien wurde die Reihenfolge der Sprecher angeblich zufällig ermittelt. Es waren von der Partei Supi 4 Vertreter anwesend und von der Partei Toll 5 Vertreter. Die Reihenfolge der Sprecher war folgendermaßen vorgegeben:

S S  T  S  T T T  S  T

Ein Vertreter von Toll beschwerte sich, dass S vorgezogen würde. Es wurde ein Runtest vorgenommen:

Es ist n₁ = 4 und n₂ = 5. Man erhielt r = 6 Runs.

Nach der Tabelle des Runstests wird H₀ abgelehnt, wenn r ≤ 2 oder r ≥ 9 ist. Also liegt die Prüfgröße r = 6 im Nichtablehnungsbereich; man kann davon ausgehen, dass die Reihenfolge der Sprecher zufällig ist.

Ergänzungen

Parameter der Verteilung von R

Der Erwartungswert von R ist

$ER={\frac {2n_{1}n_{2}}{n}}+1$

und die Varianz

$\operatorname {var} R={\frac {2n_{1}n_{2}(2n_{1}n_{2}-n)}{n^{2}(n_{1}+n_{2}-1)}}$.

Grundgesamtheit mit mehr als zwei Ausprägungen des Merkmals

Liegt eine Folge reeller Zahlen xi eines metrischen Merkmals vor, wird die Folge dichotomisiert: Man bestimmt den Median z der Stichprobe. Werte x < z werden als Kugeln 1. Sorte, Werte x > z als Kugeln 2. Sorte interpretiert. Diese dichotome Folge kann dann wieder auf Zufälligkeit getestet werden.

Liegt eine nichtnumerische Symbolsequenz mit mehr als zwei Ausprägungen vor, muss zunächst eine numerische Reihe erzeugt werden, wobei hier das Problem bestehen kann, dass die Symbole nicht geordnet werden können.

Normalapproximation

Für Stichprobenumfänge n₁,n₂ > 20 ist die Zahl der Runs R annähernd normalverteilt mit Erwartungswert und Varianz wie oben. Man erhält die standardisierte Prüfgröße

$z={\frac {r-({\frac {2n_{1}n_{2}}{n}}+1)}{\sqrt {\frac {2n_{1}n_{2}(2n_{1}n_{2}-n)}{n^{2}(n_{1}+n_{2}-1)}}}}$

Die Hypothese wird abgelehnt, wenn

$z<-z\left(1-{\frac {\alpha }{2}}\right)$ oder $z>z\left(1-{\frac {\alpha }{2}}\right)$

mit $z\left(1-{\frac {\alpha }{2}}\right)$ als Quantil der Standardnormalverteilung für die Wahrscheinlichkeit $1-{\frac {\alpha }{2}}$.

Anwendungen

Der Runtest kann angewendet werden, um Stationarität bzw. Nicht-Korrelation in einer Zeitreihe oder anderen Sequenz zu überprüfen, vor allem wenn die Verteilung des Merkmals unbekannt ist. Die Nullhypothese ist hier, dass aufeinanderfolgende Werte unkorreliert sind.

Der Run-Test ist nicht so mächtig wie der Kolmogorov-Test oder der Chi-Quadrat-Test, kann aber mit letzterem kombiniert werden, da beide Prüfgrößen asymptotisch unabhängig voneinander sind.

Beispiel für ein metrisches Merkmal

Es liegt die Folge

13	3	14	14	1	14	3	8	14	17	9	14 
	13	2	16	1	3	12	13	14

vor. Sie wird mit dem Median z = 13 dichotomisiert. Dazu wird der Median 13 von allen Werten abgezogen. Für die erste Ausprägung (Werte über Null) wird + gesetzt, für die zweite Ausprägung (Wert < 0) wird - gesetzt.

0	-10	1	1	-12	1	-10	-5	1	4	-4	1 
	0	-11	3	-12	-10	-1	0	1

+	-	+	+	-	+	-	-	+	+	-	+ 
	+	-	+	-	-	-	+	+

Man erhält bei n₁ = 11 (+) und n₂ = 9 (-) r = 13 Runs. R ist annähernd normalverteilt mit dem Erwartungswert

$ER={\frac {(2\cdot 11\cdot 9)}{20}}+1=10{,}9$

und der Varianz

$\operatorname {var} R={\frac {2\cdot 11\cdot 9\cdot (2\cdot 11\cdot 9-20)}{20^{2}\cdot 19}}\,4{,}6$.

Die Prüfgröße z errechnet sich dann als

${\frac {13-10{,}9}{\sqrt {4{,}6}}}=1{,}0$

Bei einem Signifikanzniveau von 0,05 wird H₀ abgelehnt, wenn |z| > 1,96. Dies ist nicht der Fall.

Entscheidung: Die Hypothese wird nicht abgelehnt. Die Elemente der Stichprobe sind vermutlich zufällig entnommen worden.

Programmierung des Runtestes

Zitat: Wenn du es nicht programmiert hast, dann hast du es nicht verstanden.

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 Direktfenster.

• 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 bzw hoher Ordnung. Interessant ist, daß man mit dem Vorzeichen des pz Wertes zwei Arten von Ordnung erhält:
    • wiederholende Ordnung pz > 1,5
    • symmetrische Ordnung pz < -1,5

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
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

Universelle Entropielandschaft der 01 Folgen

Ein Gletscher mit zerklüfteter Oberfläche als Beispiel für die universelle Entropielandschaft

Die Universelle Entropielandschaft der 01 Folgen zeigt die Aufspaltung der Information in ungeordnete Information und 2 verschiedene Arten von Ordnung. Dabei werden die pz-Wert mit dem oben angegebenen Listing errechnet.

Der Anfang der Landschaft ist ganz einfach. Am Anfang, bei sehr kurzen Sequenzen, ist auch noch keine Unterscheidung zwischen Zufall und Ordnung möglich.

1, 0

00, 01, 10, 11

000, 001, 010, 011, 100, 101, 110, 111

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1111

00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11111

Ab einer gewissen Länge der Sequenz kann man Ordnung von Zufall trennen.

Grafische Darstellung der Entropiewerte einer 8 Stellen langen 01 Folge

Skizze einer berechnete Ordnungs-Entropielandschaft von 01 Folgen

Werden die Sequenzen sehr lang, dann sind Ordnungsparameter wie pz nicht mehr in einem begrenzten Zeitraum berechenbar. Allerdings kann man sich dann mit Stichproben behelfen.

Grenze zwischen Zufall und Ordnung

Interessant ist, dass an der Grenze zwischen Zufall und Ordnung verwaschene Verhältnisse vorliegen. Es gilt das Tur-Tur Prinzip. Je weiter weg man von der Grenze ist, desto klarer wird die Unterscheidung, je näher man daran ist, desto unschärfer und unsicherer wird sie.

Zufall und Entropie

Zwischen dem Zufall und der Entropie, wie er in der Informationstheorie definiert wurde, besteht ein enger Zusammenhang. Entropie ist ein Maß für die Menge an Zufallsinformation, die in einem System oder einer Informationsfolge steckt.

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.

Definition der Entropie

Shannon definierte die Entropie H einer gegebenen Information I über einem Alphabet (Informatik) 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 Informationtext I auftritt. Die Entropie erhält die Pseudoeinheit bit. H multipliziert mit der Anzahl der Zeichen im Informationstext ergibt dann die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information notwendig sind.

Obige Formel ist für den mathematisch nicht vorgebildeten schwer verständlich. Sie wird leichter zu verstehen, wenn man von ganz einfachen Beispielen wie dem Münzwurf, einem Sechser- oder Achterwürfel ausgeht und die Entropie dazu berechnet. Siehe dazu die weiter unten angegebenen Beispiele.

Interpretation

Entropie ist grob gesagt ein Maß für die Menge an Zufallsinformation, die 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 2 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 etwa 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 würde. Eine angemessenere Definition der Entropie einer Zeichenkette liefert die bedingte Entropie und Quellentropie, die beide auf Verbundwahrscheinlichkeiten aufbauen.

Beispielsberechnung der Entropie: Münzwurf

Münze mit unterscheidbarer Vorder- und Rückseite

Bei einem Münzwurf sind idealerweise „Kopf“ oder „Zahl“ gleichwahrscheinlich. Indem man die Entropie als Maß für die Ungewissheit auffasst, wird sie hier daher 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ällen „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 zu Summe 1, da es nur 2 Möglichkeiten gibt.

p + q = 1

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

H = - (p * ld p + q * ld q)

Unter ld wird der Logarithmus zur Basis 2 verstanden (log dualis, binärer Logarithmus)

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

H = - (p * ld p + (1- p) * ld (1-p))

Für p = 0,5 ergibt sich beispielsweise daraus:

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

denn der Logarithmus der Zahl 0,5 zur Basis 2 ist gleich - 1.

Die Funktion der Entropie in Abhängigkeit von der Wahrscheinlichkeit kann man grafisch folgendermaßen darstellen:

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 p 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 2 mal wächst die Zahl der Möglichkeiten auf 4. 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 * 1 bit = 20 bit. Dies wird im folgenden Bild dargestellt.

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

Sei nun eine Folge von Münzwürfen als Bitfolge zu speichern. Während es sich bei der normalen Münze anbietet, „Kopf“ stets durch 0 und „Zahl“ stets durch 1 zu repräsentieren (oder umgekehrt), so sind bei der gezinkten Münze kompaktere Kodierungen möglich. Diese erhält man beispielsweise durch den Huffman-Kode.

Beispielsberechnung der Entropie: Idealer 6er Würfel

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

H = log2(Zahl der gleichberechtigten Elemente im Ergebnisraum).

Beim idealen Würfel sind 6 Möglichkeiten im Ergebnisraum. Daraus folgt die Entropie für einmal werfen:

H = log2 6 = log2 2*3 = log2 2 + log2 3 = 1 + log2 3 $\approx$ 1 + 1.585 = 2.585 bit

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

H = log2 8 = 3 bit

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

Entropie vs. Zahl der Möglichkeiten

Zufall und Ordnung

Betrachtet man eine binäre Datei einer bestimmten Länge z. B. mit 20 Stellen, dann kann man die Gesamtinformationsmenge ausrechnen, die mit 20 Stellen dargestellt werden kann:

I = 220 = 1 048 576 Bit = 217 Byte = ca. 130 KiB.

Ein Teil der Möglichkeiten aus dieser Gesamtinformationsmenge sind reine Zufallsfolgen, der Rest sind mehr oder minder geordnete Folgen. Die Grenze zwischen beiden Bereichen ist nicht scharf zu ziehen, sondern nur mit einem Wahrscheinlichkeitsniveau von z. B. 95% festzulegen. Je weiter man von der Grenze weg ist, desto klarer ist die Zuordnung. Der Mathematiker und Zufallsforscher Chaitin hat 2 Beispiele genannt:

• Geordnete Reihe: 10101010101010101010
• Zufall = 0, oder fast Null
• Ungeordnete Reihe durch Münzwurf erzeugt: 01101100110111100010
• Zufall maximal = 20 Bit

Beide Reihen haben dieselbe Länge und denselben Speicherplatzbedarf an Bits. Trotzdem unterscheiden sie sich fundamental. Die Menge an Zufall einer Reihe lässt sich durch die Entropie bzw. den Informationsgehalt quantifizieren, bezüglicher der sich beide Reihen sehr stark unterscheiden. Dies ist Gegenstand der Informationstheorie, die erstmals von Claude Shannon formalisiert wurde. Die erste Reihe hat zum Beispiel eine Entropie von 0 oder nahe 0, die zweite Reihe hat eine Entropie von 20 bit.

Eine interessante Frage ist nun, wie hoch der Anteil der Zufallsfolgen an der Zahl der gesamten Möglichkeiten ist. Eine weitere interessante Frage ist, ob man die Nichtzufälligkeit irgendwie quantifizieren kann, also ob man sagen kann: Je stärker eine nichtzufällige Reihe komprimierbar ist, desto größer ist ihre Ordnung. Die einfachste Form der Ordnung ist hier die Wiederholung von Teilstücken, man spricht auch von Redundanz.

Dann ergeben sich die allgemeinen Aussagen: Der Anteil der Zufallsfolgen wächst mit der Anzahl der Gesamtmöglichkeiten, oder anders ausgedrückt: Je länger eine binäre Sequenz ist, desto mehr Möglichkeiten für Zufallsfolgen stecken in ihr.

Je geordneter eine ganz bestimmte Binärfolge ist, desto weniger "Zufall" steckt in ihr. Vor allem in dem Begriff der Komprimierbarkeit, den man zur Definition der geordneten Folge heranzieht, stecken einige Tücken. Er ist mathematisch auf verschiedene Arten definierbar.

Bei kurzen binären Sequenzen ist die Unterscheidung zwischen Ordnung und Zufall willkürlich, je länger die Sequenzen werden, desto besser sind sie dem Bereich des Zufalls oder dem Bereich geordneter Folge zuzuordnen.

Trotzdem bleiben auch bei längeren Folgen von Nullen und Einsen Überlappungen zwischen geordneten Folgen und Zufallsfolgen bestehen. Jede geordnete binäre Folge kann mittels eines guten Komprimierungsverfahrens in eine scheinbare Zufallsfolge überführt werden.
Das Ergebnis sieht dann zwar zufällig aus, in ihm steckt aber bedeutsame Information.

Umgekehrt kann man mittels komplizierter Rechenverfahren Zufallszahlen erzeugen, die ausschauen wie echte (z. B. gewürfelte) Zufallszahlen, die aber in Wirklichkeit das Ergebnis eines festgelegten Algorithmus sind).

Mathematische Definition von Ordnung

Mit dem Begriff  Ordnung verbinden sich ganz verschiedene Vorstellungen. Selten findet man eine brauchbare mathematische Definition. Will man Ordnung (wie es beispielsweise die Kristallchemie tut) als Gegensatz von Entropie ansehen, dann kann man folgende Formel aufstellen

O = 1/ H    Ordnung = 1 / Entropie     daraus folgt  Entropie = 1 / Ordnung

Die Ordnung ist hier der Kehrwert der Entropie. Mit dieser Definition gibt es ein Problem: Bei einer Entropie von 0 wird die Ordnung unendlich groß.

Als Beispiel wird eine 40er Folge von 1 und 0 betrachtet:

• reiner Zufall: Entropie = 40 Bit, das heißt die Ordnung ist sehr niedrig
  • 1011011010101001110010110011100000011110
• reine Ordnung: Entropie = 0 Bit, das heißt die Ordnung ist maximal
  • 1111111111111111111111111111111111111111
  • 0000000000000000000000000000000000000000

Wie soll man dann Ordnung definieren?

O = 1 / H daraus folgt eine Spannweite der Ordnung von O = 1/40 bis O = Unendlich

Wahrscheinlich ist folgende Lösung besser:

O = 1 / (H + 1) daraus folgt eine Spannweite der Ordnung von O = 1/41 bis O = 1

Abgeleitet davon kann man die Ordnung als Prozentwert angeben:

O = 100 / (H + 1) % 

daraus folgt eine Spannweite der Ordnung von O = 100 /41 % = 2,5 % Ordnung bis 100 % Ordnung

Beispiele für geordnete und nicht geordnete Strukturen

Eigentlich hat Chaitin bei seinen treffenden Beispielen noch etwas vergessen: Zwischen perfekter Ordnung und kompletter Zufallsordnung, gibt es noch gemischt geordnete Strukturen.

Abbildung 0:

Hohe Ordnung : Entropie nahe Null : symmetrische Ordnung

1111111111111111111111111111111100000000000000000000000000000000 

Abbildung 1:

Hohe Ordnung , entspricht Chaitin Kette A , Entropie nahe Null : Wiederholende Ordnung

0101010101010101010101010101010101010101010101010101010101010101 

Abbildung 2:

In sich geschlossene Ordnung höhererArt , komplizierte Ordnung mit Symmetrie

1111111110000001100001011000100110010001101000011000000111111111 

Abbildung 3:

Logische Ordnung höherer Art , Logische Folge zB binäre Zahlen von 0000 bis 1111

0000000100100011010001010110011110001001101010111100110111101111 

Abbildung 4:

Zufallsequenz, Entropie maximal , 64 bit , Ordnung sehr gering, entspricht Chaitin B Kette

0100111110101110101000010101001101011010001100101110010000010111

Pi und der Zufall

apple pi e, zwischen Kulinarik und Pi herrscht ein entspanntes Verhältnis

Bis jetzt ist es nicht gelungen, in den Nachkommastellen der Kreiszahl Pi eine mathematische Ordnung oder periodische Wiederholung zu erkennen. Dies spricht sehr dafür, das die Nachkommastellen eine Zufallsfolge darstellen.

Es geht darum, ob die Zahl Pi eine  normale Zahl ist. Normal ist eine Zahl im mathematischen Sinne dann, wenn alle Ziffern und Ziffernblöcke in ihrer Zahlenfolge in gleicher Häufigkeit auftreten und diese zufällig verteilt sind.

Ist die Zahl Pi komprimierbar ?

Findige Köpfe haben die Zahl Pi als ein Gegenbeispiel der Aussage herangezogen, daß zufällige Zahlenfolgen nicht komprimierbar sind. Die Nachkommastellen von Pi sind zufällig, gleichzeitig kann man aber eine Rechenvorschrift angeben, mit der man die Nackommastellen mit einer Formel beliebig genau berechnen kann. Der Informationsgehalt der Formel erscheint dabei weit gering zu sein, als die die ausgeschriebene Zahl selbst. Wie diese Diskussion letztendlich ausgeht, ist noch nicht sicher. Es ist jedenfalls eine spannende Frage, die das Komprimierbarkeitskriterium zur Definition von nichtzufällige Informationssequenzen in seiner allgemeinen Form relativiert.

Weitere Fragen zur Zufälligkeit von Pi

Ab welcher Nachkommastelle läßt sich die Zufälligkeit von Pi nachweisen ? Oder kann man schon 3,14 in die Zufallsrechnung mit einbeziehen ? Wenn die Nachkommastellen von Pi eine zufällige Folge sind, kann man dann jede beliebige gute Zufallsfolge dafür einsetzen d.h. kann man Zufall durch Zufall ersetzen ?

Links und Quellen zu Pi und der Zufall

• http://www.spiegel.de/wissenschaft/mensch/mathematik-enthaelt-die-zahl-pi-ein-geheimes-muster-a-353818.html
• http://www.ernst-team.de/texte/pi_5.pdf
  • Die Zahl Pi und der Zufall
• http://www.scinexx.de/dossier-detail-389-6.html
  • Wie normal ist Pi ?
• David H. Bailey and Richard E. Crandall,
  • On the Random Character of Fundamental Constant Expansions", Experimental Mathematics, vol. 10, no. 2 (June 2001), pg. 175-190;

e und der Zufall

Annäherung an e

Bis jetzt ist es nicht gelungen, in den Nachkommastellen der  Eulerschen Zahl e eine mathematische Ordnung oder periodische Wiederholung zu erkennen. Dies spricht sehr dafür, das die Nachkommastellen eine Zufallsfolge darstellen.

Es geht darum, ob die Zahl e eine  normale Zahl ist. Normal ist eine Zahl im mathematischen Sinne dann, wenn alle Ziffern und Ziffernblöcke in ihrer Zahlenfolge in gleicher Häufigkeit auftreten und diese zufällig verteilt sind.

Links und Quellen zur Zahl e und der Zufall

• • On the Random Character of Fundamental Constant Expansions", Experimental Mathematics, vol. 10, no. 2 (June 2001), pg. 175-190;

Literatur

•  Kategorie Stochastik in Wikipedia
•  Kategorie stochastischer Prozeß in Wikipedia
• Bradley, (1968). Distribution-Free Statistical Tests, Chapter 12.
• Entropy tests for random number generators
  • http://www-perso.iro.umontreal.ca/~lecuyer/myftp/papers/entrop.ps
• Estimation of the Kolmogorov entropy from a chaotic signal
  • Peter Grassberger
  • Physics Department, University of Wuppertal, D-5600 Wuppertal 1, Germany
  • Itamar Procaccia
  • Chemical Physics Department, Weizmann Institute of Science, Rehovot 76100, Israel
    • A new method for estimating the Kolmogorov entropy directly from a time signal is proposed and tested on examples. The method should prove valuable for characterizing experimental chaotic signals.
• Siehe auch: http://www.itl.nist.gov/div898/handbook/eda/section3/eda35d.htm

Links

•  /dev/random
  • liefert Zufallszahlen unter Unix und Linux
• Gambas: Zufall
  • Basic Programme zum Thema Zufall mit Quellcode und Bildern.