Wie Zufallszahlengeneratoren funktionieren und woran du erkennst, ob einer fair ist

Wenn du bei einem Zufallszahlengenerator auf „Generieren“ klickst, erzeugt ein Computer, der eigentlich dafür gebaut ist, Anweisungen exakt zu befolgen, etwas, das niemand vorhersagen kann. Diese Anleitung erklärt, wie das funktioniert, welcher Fehler einen Generator am häufigsten unbemerkt unfair macht und wie du beurteilen kannst, ob Ergebnisse zufällig sind.

Drei Arten von Zufall

Pseudozufallszahlengeneratoren

Ein Pseudozufallszahlengenerator (PRNG) ist eine Formel. Er beginnt mit einem Startwert, dem sogenannten Seed, und formt ihn immer wieder um, sodass eine Folge entsteht, die zufällig aussieht. Mit demselben Seed erzeugt er exakt dieselbe Folge noch einmal. Das ist praktisch für Simulationen und Videospiele, die reproduzierbare Ergebnisse brauchen.

Math.random() in JavaScript ist ein PRNG. Für Animationen und Gelegenheitsspiele ist er völlig in Ordnung. Browser garantieren jedoch nicht, dass seine Ausgabe unvorhersehbar ist, und die Spezifikation schreibt keine bestimmte Qualität vor. Für Passwörter, Gewinnziehungen oder alles, bei dem jemand vom Erraten des nächsten Ergebnisses profitieren könnte, sollte er nicht verwendet werden.

Kryptografisch sichere Generatoren

Ein kryptografisch sicherer PRNG (CSPRNG) ist so konstruiert, dass frühere Ausgaben nicht helfen, die nächste vorherzusagen. Betriebssysteme speisen ihn aus unvorhersehbaren physikalischen Ereignissen wie Zeitrauschen der Hardware und mischen fortlaufend neue Entropie hinzu. Im Browser steht er über die Web Crypto API als crypto.getRandomValues() zur Verfügung.

Hardware-Zufallszahlengeneratoren

Ein Hardware-Generator misst einen physikalischen Vorgang, etwa elektrisches Rauschen, und wandelt ihn in Bits um. Moderne Prozessoren enthalten einen solchen Generator, und Betriebssysteme kombinieren seine Ausgabe mit anderen Quellen, um ihren CSPRNG zu speisen. Die meisten Menschen müssen nie direkt darauf zugreifen.

Was Randomify verwendet: Jedes Ergebnis stammt aus crypto.getRandomValues() in deinem eigenen Browser, was alle aktuellen Browser unterstützen. Die Zahlen werden auf deinem Gerät erzeugt, und Listen, die du eingibst, werden zum Erzeugen eines Ergebnisses nicht hochgeladen.

Die versteckte Unfairness: der Modulo-Bias

Eine Zufallsquelle liefert Bits, nicht „eine Zahl von 1 bis 6“. Bei der Umwandlung des einen in das andere machen viele Generatoren Fehler.

Angenommen, eine Quelle liefert ein zufälliges Byte, also eine ganze Zahl von 0 bis 255, und ein Programm braucht einen Würfelwurf. Die Abkürzung besteht darin, den Rest bei Division durch 6 zu nehmen und 1 zu addieren. Aber 256 ist kein Vielfaches von 6: 256 = 42 × 6 + 4. Die Reste 0, 1, 2 und 3 entstehen auf jeweils 43 Arten, 4 und 5 dagegen nur auf 42. Die Augenzahlen 1 bis 4 sind dadurch etwas wahrscheinlicher als 5 und 6.

Der Unterschied ist klein, 43/256 statt 42/256, aber es ist eine systematische Verzerrung und keine zufällige Schwankung. Je größer der Bereich im Verhältnis zur Quelle ist, desto stärker wird die Verzerrung.

Die Lösung heißt Rejection Sampling (Verwerfungsmethode): Jeder Rohwert aus dem unvollständigen letzten Block wird verworfen und neu gezogen. Im Byte-Beispiel werden nur die Werte 0 bis 251 akzeptiert, sodass jede Augenzahl auf genau 42 Arten entstehen kann. Randomify verwendet 32-Bit-Werte mit Rejection Sampling, sodass jede Zahl in deinem Bereich gleich wahrscheinlich ist.

Probiere es mit einem beliebigen Bereich aus:

Fair mischen

Wer Namen aus einer Liste zieht oder Personen in Teams aufteilt, braucht ein faires Mischen: Jede mögliche Reihenfolge sollte gleich wahrscheinlich sein.

Die Standardmethode ist der Fisher–Yates-Shuffle. Beginnend beim letzten Element wird es mit einem Element vertauscht, das gleichverteilt zufällig aus den noch nicht festgelegten Elementen (einschließlich sich selbst) gewählt wird; danach rückt man eine Position nach links. Bei n Elementen erzeugt das jede der n! möglichen Reihenfolgen mit gleicher Wahrscheinlichkeit.

Eine beliebte Abkürzung ist, eine Liste mit zufälligen Vergleichen zu sortieren. Das liefert keine gleich wahrscheinlichen Reihenfolgen, und die Verzerrung hängt vom Sortieralgorithmus ab. Der Namens-Picker und der Team-Generator von Randomify verwenden Fisher–Yates.

Zufallsergebnisse wirken weniger zufällig, als man erwartet

Menschen erwarten meist, dass sich Ergebnisse in Zufallsfolgen häufiger abwechseln, als sie es tatsächlich tun. Eine echte Zufallsfolge enthält Serien, Häufungen und Wiederholungen.

Sechsmal Kopf in Folge bei hundert Würfen ist also kein Hinweis auf ein Problem; dass es nicht vorkommt, wäre eher überraschend. Dasselbe gilt, wenn ein Zufallszahlengenerator zweimal hintereinander dieselbe Zahl liefert. Bei einem Bereich von 1 bis 10 passiert das bei etwa jeder zehnten Ziehung.

Probiere es selbst: Wirf 100 Münzen auf einmal und suche nach der längsten Serie.

So prüfst du, ob ein Generator fair ist

Aus wenigen Ergebnissen lässt sich nicht beweisen, dass ein Generator fair ist, aber offensichtliche Probleme kannst du erkennen:

1. Sammle viele Ergebnisse. Kleine Stichproben schwanken stark. Sammle bei einem Generator für 1–6 Hunderte oder Tausende Ziehungen, nicht zwanzig.
2. Vergleiche die Häufigkeiten mit den Erwartungen. Jeder Wert sollte ungefähr gleich oft vorkommen. In der Statistik misst man mit einem Chi-Quadrat-Test, ob die Abweichungen größer sind, als der Zufall üblicherweise hervorbringt.
3. Betrachte Folgen, nicht nur Häufigkeiten. Ein Generator könnte perfekte Häufigkeiten liefern, indem er immer 1, 2, 3, 4, 5, 6 durchläuft. Prüfe also auch Wiederholungen und Serien.
4. Frag nach, wie er funktioniert. Ein vertrauenswürdiges Werkzeug sollte angeben, welche Zufallsquelle es verwendet und wie es sie auf einen Bereich abbildet.

Für Anwendungen, bei denen viel auf dem Spiel steht, etwa Sicherheitsschlüssel, gesetzlich regulierte Ziehungen oder wissenschaftliche Stichproben, solltest du einen dokumentierten Generator verwenden, der den einschlägigen Standard erfüllt, und den Ablauf protokollieren.

Häufig gestellte Fragen

Ist eine Zufallszahl aus dem Computer wirklich zufällig? Ein CSPRNG ist deterministisch, sobald er einen Seed hat, aber dieser Seed stammt aus physikalischer Unvorhersehbarkeit, und ohne den internen Zustand lässt sich seine Ausgabe praktisch nicht vorhersagen. Für alltägliche Ziehungen, Spiele und Passwörter ist er die richtige Wahl.

Kann ich ein Ergebnis später reproduzieren? Mit einem kryptografischen Generator nicht, und das ist so gewollt. Um eine Ziehung überprüfbar zu machen, zeichne sie auf dem Bildschirm auf oder lass Zeugen dabei sein, wie in Wie du eine faire Online-Verlosung durchführst beschrieben.

Warum habe ich zweimal dieselbe Zahl bekommen? Weil jede Ziehung unabhängig ist. Deaktiviere Duplikate, wenn jedes Ergebnis verschieden sein muss, zum Beispiel beim Ziehen mehrerer Gewinner.