Qualität von Zufallszahlen

Für den gemeinsamen Spielabend reichen in der Regel die alten, namensgebenden, sechsseitigen Objekte aus. Im Spielcasino kommen extrem scharfkantig geschliffene Würfel zum Einsatz und werden nach einigen Runden der Benutzung auch noch ausgetauscht. In der Kryptographie – mit der man tagtäglich mehr zu tun hat als mit irgendeinem Spiel – erzeugt man den erforderlichen Zufall mit einer Rechenformel, die weit weg von einem klassischen Würfel und damit dem eigentlichen Zufall ist.

Die Erzeugung von Zufallszahlen basiert auf gruppentheoretischen Modellen, elliptischen Kurven und dergleichen mehr und ist damit eine Wissenschaft für sich. Die Zufallszahlengeneratoren haben allerdings einen Fakt gemeinsam: Sie basieren auf eine Funktion und sind damit berechenbar und im schlimmsten Fall vorhersagbar.

Wie schlimm es um den Zufallszahlengenerator bestellt ist, ist ebenfalls wieder eine Wissenschaft für sich, doch ein paar einfache Tests lassen sich auch ohne dieses Wissen durchführen.

Für Zufallszahlen hat man im wesentlichen zwei relevante Anforderungen:

  1. Alle möglichen Zufallszahlen müssen bei einer ausreichend großen Zahl an Ziehungen gleich häufig auftreten. (Gleichverteilung)
  2. Nach einer Ziehung mit bestimmten Resultat müssen darauffolgende Zufallszahlen ebenfalls gleich häufig verteilt vorkommen. (Unvorhersagbarkeit)

Gleichverteilung

Die erste Anforderung ist leicht zu erklären: Würfelt man mit einem konventionellen, sechsseitigen Würfel 6.000.000 mal, so sollte jede Augenzahl ungefähr 1.000.000 mal aufgetaucht sein. Wichtig ist hier die größte der Stichprobe, denn würfelt man den Cubus nur sechs mal, kann es zwar vorkommen, dass jede Zahl exakt einmal geworfen wurde, doch wahrscheinlicher ist, dass eine Zahl häufiger fällt, als andere.

Mit dem Online Würfel Tool kann man dies schnell simulieren. Bei meinem Versuch sechs sechsseitige Würfel zu werfen (6W6) erhielt ich die folgenden Resultate:

Werfe 6W6
Ergebnisse:
6 2 4 4 3 4

Ganz offensichtlich haben wir hier keine Gleichverteilung, denn die 4 wurde dreimal geworfen, die 1 und 5 hingegen nicht ein einziges mal.

Wiederholt man den Versuch mit einer größeren Zahl an Würfen (z.B.: 1000W6), so sieht das Resultat schon besser aus:

Werfe 1000W6
Ergebnisse:
2 5 3 2 3 5 2 3 1 1 6 6 1 4 3 3 5 4 1 4 4 6 6 4 2 3 5 2 5 6 6 3 6 3 2 4 4 6 1 6 4 6 1 3 4 4 5 1 3 5 1 3 3 2 2 4 5 1 3 5 5 1 3 6 5 4 3 2 2 3 2 1 1 1 4 5 5 4 4 6 5 2 2 4 6 3 6 3 3 4 2 2 3 3 3 5 5 2 4 1 2 6 2 2 1 3 3 2 2 5 3 5 3 2 3 5 3 3 4 3 2 3 1 2 3 1 5 5 5 3 2 5 1 2 3 6 4 3 2 1 4 3 4 3 3 3 4 5 6 1 5 2 5 1 5 4 6 3 4 5 6 4 1 4 5 4 5 3 6 4 2 6 4 3 1 5 5 6 1 4 6 5 2 1 3 1 1 6 3 3 6 6 5 5 3 2 1 6 4 3 6 2 6 5 3 6 2 4 1 3 2 6 3 2 2 5 4 5 6 2 5 6 6 5 5 1 6 5 2 3 4 3 2 4 4 3 3 3 3 6 6 6 3 5 3 1 6 1 2 6 3 4 5 1 1 3 2 1 6 2 5 6 6 5 1 1 3 5 5 1 2 5 5 2 4 1 6 1 6 1 2 3 6 2 4 3 2 6 5 2 3 4 6 6 4 4 4 3 1 6 1 2 6 2 2 4 2 6 4 1 4 2 6 4 1 1 4 1 5 2 5 1 6 2 6 1 5 6 2 1 5 2 1 6 6 4 4 3 6 3 3 3 3 6 3 6 5 1 6 3 6 3 1 6 4 1 3 2 6 6 6 5 5 1 6 6 4 3 4 5 1 3 6 4 2 3 6 4 1 6 3 1 1 4 3 5 5 4 2 1 2 1 3 6 5 6 6 2 2 3 1 4 3 1 4 1 4 3 5 5 1 4 4 2 3 6 1 5 4 5 6 6 2 4 4 1 1 6 2 4 3 1 1 4 4 2 6 1 5 6 5 1 3 5 4 4 4 1 2 2 3 5 1 1 5 5 5 6 6 6 1 4 6 6 3 3 2 3 4 4 4 3 6 5 6 2 5 1 4 4 6 1 3 4 4 4 6 2 1 2 1 6 2 6 1 6 5 5 2 2 1 4 6 2 1 5 1 1 5 1 1 5 6 5 3 4 2 5 1 4 4 6 6 6 6 6 1 1 3 6 5 4 3 4 4 3 1 1 4 5 3 5 5 2 2 1 1 4 6 6 6 3 1 5 5 2 3 1 2 2 1 1 6 1 1 1 3 5 4 3 6 6 5 3 6 3 5 2 4 6 5 2 5 3 2 5 6 1 5 1 1 5 4 4 1 2 3 3 5 3 1 3 6 2 4 3 6 5 3 5 1 1 2 2 4 4 4 1 1 4 5 1 5 4 2 6 4 5 1 6 2 6 3 6 6 2 3 6 6 1 3 5 2 4 4 3 2 3 3 2 2 3 6 3 5 3 4 5 4 6 6 1 6 5 4 2 1 3 5 6 4 3 4 4 3 2 5 1 1 4 2 3 1 1 1 1 4 3 4 2 6 1 2 5 5 4 5 6 2 4 1 6 3 5 4 6 1 1 5 5 1 4 6 3 1 3 5 3 4 4 3 1 2 1 6 4 5 5 6 4 5 4 4 6 4 6 3 1 5 5 4 6 6 3 6 2 3 3 3 6 1 2 5 3 1 4 5 4 4 1 5 1 3 3 6 2 2 6 5 3 2 6 6 1 3 1 3 2 1 3 6 5 4 2 2 4 3 6 3 5 4 6 5 6 6 6 5 4 4 2 2 5 4 5 1 5 3 5 1 6 1 6 6 6 1 6 1 3 4 1 3 3 5 6 6 4 2 5 5 5 5 5 6 4 2 2 4 1 1 2 6 2 1 4 4 4 6 5 4 3 1 1 1 5 3 4 1 5 1 5 3 1 2 5 1 6 3 4 2 1 1 3 6 5 3 5 3 5 4 1 2 4 5 4 6 3 3 5 5 6 5 4 6 6 5 1 2 3 5 2 2 3 5 4 1 4 5 3 3 3 6 4 2 2 5 5 3 1 5 1 6 3 1 4 6 1 3 2 3 4 6 4 4 6 6 5 3 2 1 2 5 6 5 4 6 6 1 4 3 3 1 6 4 4 5 5 6 6 6 3 2 5 2 5 2 5 5 1 6 4 3 4 5 6 1 2 3 6 6 4 6 1 1 1 1 2 1 3 5 2 5 1 6 3 1 6 3 6 3 3

Da das auszählen der Ergebnisse von Hand äußerst mühsam ist, gibt es im Online Würfel Tool das Kommando “statistics” mit dem eine Auswertung alle in der Sitzung getätigten Würfe gefahren werden kann.

Wüfelstatistik:
W6 wurde 1000 mal geworfen. Ergebnisse:
1 fiel 174 mal = 17.4%
2 fiel 136 mal = 13.6%
3 fiel 176 mal = 17.6%
4 fiel 161 mal = 16.1%
5 fiel 169 mal = 16.9%
6 fiel 184 mal = 18.4%
Sollwert je Ergebnis: 16.7%

Die Streuung bei den Augenzahlen ist immer noch vergleichsweise hoch, doch die Zahl der Würfe, die jetzt schon der Anzahl an einem normalen Spielabend übersteigt, ist für einen Statistiker noch lange nicht ausreichend.

Würfelt man noch 99.000 weitere Male, so bewegt man sich schon eher im Zielkorridor:

Wüfelstatistik:
W6 wurde 100000 mal geworfen. Ergebnisse:
1 fiel 16729 mal = 16.7%
2 fiel 16690 mal = 16.7%
3 fiel 16644 mal = 16.6%
4 fiel 16778 mal = 16.8%
5 fiel 16505 mal = 16.5%
6 fiel 16654 mal = 16.7%
Sollwert je Ergebnis: 16.7%

Der Unterschied bei den Häufigkeiten zur erwarteten Anzahl liegt bei maximal 0,2 Prozentpunkten. (Bei weiteren Versuchen mit dieser Anzahl an Würfen war es sogar noch weniger.)

Da die Zufallszahlen mit gleicher Wahrscheinlichkeit fallen sollen, lässt sich die zu erwartende Anzahl recht einfach berechnen: Anzahl der Würfe/Anzahl der möglichen Ergebnisse. Im Fall der 100.000 Würfe mit sechsseitigen Würfeln also frac{100000}{6}=16666.7.

Eine Probe auf Gleichverteilung von Zufallszahlen ist also durch Führen einer einfachen Strichliste einfach zu realisieren.

Unvorhersagbarkeit

Die zweite und wahrscheinlich noch gewichtigere Anforderung hingegen kann nur mit einer erheblich komplexeren Liste, bzw. einer Matrix nachvollzogen werden. Die spannende Frage, die es hier zu klären gilt, ist, ob nach einer Zahl x die nächste Zahl immer noch gleichverteilt ist.

Falls dem nicht so ist, könnte ein aufmerksamer Spieler anhand einer gefallenen Zahl auf das nächste Resultat schließen. Auch wenn das nächste Ergebnis nicht zu 100% sicher ist, wäre mit einer signifikant erhöhten Wahrscheinlichkeit doch Profit zu machen.

Bei einem Zufallszahlengenerator ist dieses Phänomen nicht unwahrscheinlich und ganz sicher nicht gewünscht. Die Funktion f(x_i)=(x_{i-1}+4) mod 6 +1 liefert zwar der ersten Anforderung entsprechend in der Gesamtsicht gleichverteilte Resultate, doch deren Ergebnisse sind massiv voneinander abhängig, so dass eine Voraussage der nächsten Zahl zu 100% möglich ist. (Bei der hier angegebenen Funktion handelt es sich um keine Formel eines ernsthaften Zufallszahlengenerators, sie dient lediglich der noch im Kopf möglichen Nachvollziehbarkeit.)

Um nun also zu verifizieren, ob Zahlen unabhängig von ihren Vorgängern sind, muss gezählt werden, die oft welche Zahl nach einer bestimmten vorausgehenden Zahl erscheint.

Für 100.000 Einzelwerte aus dem Online Würfel Tool (100000W6), also Ziffern 1 bis 6 mit dem Zufallszahlengenerator in JavaScript erzeugt, erhält man die folgende Matrix:

Vorgänger # 1 2 3 4 5 6
1 16618 2744 2805 2744 2753 2759 2813
2 16683 2775 2720 2871 2826 2844 2647
3 16706 2770 2807 2808 2686 2872 2762
4 16660 2806 2767 2672 2869 2700 2846
5 16720 2744 2861 2809 2810 2716 2780
6 16613 2779 2723 2801 2716 2829 2765
Vorgänger # 1 2 3 4 5 6
1 16.6% 16.5% 16.9% 16.5% 16.6% 16.6% 16.9%
2 16.7% 16.6% 16.3% 17.2% 16.9% 17.0% 15.9%
3 16.7% 16.6% 16.8% 16.8% 16.1% 17.2% 16.5%
4 16.7% 16.8% 16.6% 16.0% 17.2% 16.2% 17.1%
5 16.7% 16.4% 17.1% 16.8% 16.8% 16.2% 16.6%
6 16.6% 16.7% 16.4% 16.9% 16.3% 17.0% 16.6%

Zu lesen sind die beiden Tabellen wie folgt: Nach einer Zahl (erste Spalte, Vorgänger) folgen bei 100.000 Proben den Spalten 1-6 entsprechend häufig die unterschiedlichen anderen Zahlen. Nach einer zwei folgten also insgesamt 2.871 ( 17,2%) mal die drei, aber nur 2.647 (15,9%) mal die sechs.

Die zweite Spalte gibt die absolute, bzw. in der unteren Tabelle die relative Häufigkeit der Zahl in Spalte 1 (Vorgänger) überhaupt an. Die 3 ist in dieser Stichprobe bei 100.000 Proben exakt 16.706 mal , bzw. in 16,7% der Fälle gefallen.

Die Ziffern 1-6 kommen also erwartungsgemäß mit einer Häufigkeit von 16,7% gleichverteilt vor. Außerdem ist eine Voraussage der nächsten Ziffer durch die wiederum auf hier gegebenen Gleichverteilung (16,7%) nicht möglich, wenngleich bei dieser Stichprobe eine Spannbreite von 1,3 Prozentpunkte für den Nachfolger der Ziffer 2 gegeben ist. Bei einem weiteren Durchlauf mit 1 Mio. Ziffern lag die Spannbreite mit Werten von 16,5% bis 16,8% bei lediglich 0,3 Prozentpunkten.

Zur Unvorhersagbarkeit gehört auch die Wiederholungsfreiheit. Hierbei ist zu verstehen, ob sich eine ganze Zahlensequenz oder gar die gesamte Zufallszahlenkette nach einer bestimmten Anzahl vollständig wiederholt. Bei mathematisch erzeugten Zufallszahlen ist dies leider bislang nicht auszuschließen. Zwar sind die Algorithmen dermaßen entwickelt, dass sich die Zufallszahlen in ihrer Reihenfolge erst nach einer unvorstellbar großen Anzahl wiederholen werden, doch faktisch tun sie dies. Eine Folge von Zufallszahlen auf Wiederholungen hin zu prüfen ist ungemein komplexer.

Für handelsübliche Lösungen mit Ziffern (einstellige Zahlen) ist der JavaScript Zufallszahlengenerator durchaus passabel und möglicherweise sogar besser als manch ein Würfel. Wie man die Qualität eines Würfels überprüft, ohne diesen eine Million mal zu werfen, ist möglicherweise Thema eines zukünftigen Beitrags.

Pi

Die statistische Auswertung habe ich einmal über die ersten 100.001 Ziffern der Zahl Kreiszahl Pi (3,1415926536…) laufen lassen. Das Ergebnis hat mich dann doch überrascht:

Vorgänger # 0 1 2 3 4 5 6 7 8 9
0 9999 998 1027 962 993 968 1007 1009 1017 1001 1017
1 10137 1042 1034 992 1010 1030 971 982 1008 1044 1024
2 9908 974 1064 971 966 943 1003 1048 1017 955 967
3 10026 979 975 994 1008 1041 1075 965 1009 982 998
4 9971 1020 1001 987 1014 971 962 1033 1008 975 1000
5 10026 966 966 1029 1031 1019 1015 1017 1004 1008 971
6 10029 1054 1012 1048 997 1020 998 953 972 949 1025
7 10025 948 1046 981 1031 945 961 1100 1012 1040 961
8 9978 1011 996 992 946 1001 1020 970 1044 1027 971
9 9902 1007 1016 952 1029 1033 1014 952 934 997 968
Vorgänger # 0 1 2 3 4 5 6 7 8 9
0 10.0% 10.0% 10.3% 9.6% 9.9% 9.7% 10.1% 10.1% 10.2% 10.0% 10.2%
1 10.1% 10.3% 10.2% 9.8% 10.0% 10.2% 9.6% 9.7% 9.9% 10.3% 10.1%
2 9.9% 9.8% 10.7% 9.8% 9.7% 9.5% 10.1% 10.6% 10.3% 9.6% 9.8%
3 10.0% 9.8% 9.7% 9.9% 10.1% 10.4% 10.7% 9.6% 10.1% 9.8% 10.0%
4 10.0% 10.2% 10.0% 9.9% 10.2% 9.7% 9.6% 10.4% 10.1% 9.8% 10.0%
5 10.0% 9.6% 9.6% 10.3% 10.3% 10.2% 10.1% 10.1% 10.0% 10.1% 9.7%
6 10.0% 10.5% 10.1% 10.4% 9.9% 10.2% 10.0% 9.5% 9.7% 9.5% 10.2%
7 10.0% 9.5% 10.4% 9.8% 10.3% 9.4% 9.6% 11.0% 10.1% 10.4% 9.6%
8 10.0% 10.1% 10.0% 9.9% 9.5% 10.0% 10.2% 9.7% 10.5% 10.3% 9.7%
9 9.9% 10.2% 10.3% 9.6% 10.4% 10.4% 10.2% 9.6% 9.4% 10.1% 9.8%

Die Ziffern der Zahl Pi sind offensichtlich nicht nur nahezu gleichverteilt, sondern auch noch absolut unabhängig vom Vorgänger. Wäre die Zahl Pi nicht so starr festgelegt, gäbe ihre Berechnung wohl einen vergleichsweise guten Zufallszahlengenerator ab.

Auswertungs Tool

Über das folgende Formular kann eine eigene Statistik gefahren werden. In das Textfeld sollten die Zahlenwerte eingefügt werden und anschließen über den Button “Auswertung starten” die Berechnung angestoßen werden. Die Zahlen müssen voneinander beliebig getrennt sein (Zwischen je zwei Zahlen sollte sich also ein Nicht-Zahl-Zeichen befinden). Möchte man nur die Ziffern 0-9 auswerten, kann dies durch setzen des entsprechenden Häkchens erfolgen. In diesem Fall müssen die einzelnen Ziffern nicht voneinander getrennt sein.


Nur Ziffern

Schreibe einen Kommentar

Nutze dieses Kommentarfeld um deine Meinung oder Ergänzung zu diesem Beitrag kundzutun. Verhalte dich bitte respektvoll und höflich! Kommentare werden vor der Veröffentlichung in der Regel moderiert und bei Verstößen gegen geltendes Recht, die guten Sitten, fehlendem Bezug oder missbräuchlicher Verwendung nicht freigegeben oder gelöscht.
Über die Angabe deines Namens, deiner E-Mail Adresse und deiner Webseite freuen wir uns, doch diese Felder sind optional. Deine E-Mail Adresse wird dabei zu keinem Zeitpunkt veröffentlicht.

Um mit dem Betreiber dieser Seite nicht-öffentlich in Kontakt zu treten, nutze die Möglichkeiten im Impressum.