Warum eine Auswahl nur so fair ist wie ihre Zufallsquelle

„Es ist zufällig“ ist eine Behauptung, keine Tatsache. Zwei Dinge müssen zutreffen, damit eine Auswahl fair ist: Die Quelle der Zahlen darf nicht vorhersehbar sein, und jede Option muss gleich wahrscheinlich sein.

Beides ist umsetzbar, beides wird häufig falsch gemacht, und beides scheitert unabhängig voneinander. Ein Tool kann eine hervorragende Zufallsquelle und eine verzerrte Zuordnung haben, oder eine perfekt gleichverteilte Zuordnung, gespeist aus vorhersehbaren Zahlen.

Woher Zufälligkeit kommt

Echte Zufälligkeit kommt aus physikalischen Prozessen, die nicht durch einen vorherigen Zustand bestimmt sind:

• Radioaktiver Zerfall — der Moment, in dem ein Atom zerfällt, lässt sich nicht vorhersagen
• Thermisches Rauschen — zufällige Spannungsschwankungen in einem Widerstand
• Atmosphärisches Rauschen — Hintergrundrauschen durch Blitzaktivität
• Quantenmessung — Ergebnisse, die wirklich unbestimmt sind

Ein Computer kann diese nicht direkt beobachten. Was er tut, ist, einen Hardware-Generator abzutasten — /dev/urandom und seine Entsprechungen —, der selbst aus physikalischen Prozessen gespeist wird. Das ist ein echter Zufallszahlengenerator.

Der weitaus häufigere Fall ist ein Pseudozufallszahlengenerator: ein deterministischer Algorithmus, der eine Sequenz erzeugt, die lediglich zufällig aussieht.

next = (previous × multiplier + increment) mod modulus

Die entscheidende Eigenschaft ist nicht subtil. Wenn Sie den Algorithmus und den Startwert kennen, können Sie jeden Wert berechnen, den die Sequenz jemals erzeugen wird. Nicht ungefähr — exakt. Deshalb ist Math.random(), das die meisten Websites verwenden, für alles ungeeignet, was zählt: Seine Ausgabe wird durch den internen Zustand bestimmt, und diesen Zustand aus beobachteten Ausgaben wiederherzustellen, macht jedes künftige Ergebnis vorhersagbar.

Der Mittelweg, der die Frage entscheidet

Moderne Plattformen nutzen nicht bei jedem Aufruf rohe Hardware-Entropie. Sie nutzen einen kryptografisch sicheren PRNG — deterministisch, aber aus Hardware-Entropie gespeist und so entworfen, dass die Beobachtung der Ausgaben den Zustand nicht offenlegt.

Ein CSPRNG ist in genau dem Sinn deterministisch, in dem jede Software, die Sie nutzen, deterministisch ist. Was ihn akzeptabel macht, ist, dass sein Zustand aus dem, was er bereits ausgegeben hat, nicht wiederherstellbar ist.

Browser stellen dies über crypto.getRandomValues() bereit. Das ist die Quelle, die die Ziehungen hier nutzen.

Gleichverteilung ist ein separates Problem

Eine gute Quelle zu haben, reicht nicht. Die Zuordnung von einer Zufallszahl zu einer Auswahl kann immer noch verzerrt sein, und das ist der Fehler, den die meisten Tools machen.

Der naive Ansatz — einen zufälligen Gleitkommawert von 0 bis 1 auf den Bereich abbilden — verzerrt das untere Ende. Bei 40 Namen landen einige Zufallswerte hinter dem Ende des letzten Abschnitts, und wenn sie begrenzt statt verworfen werden, kommt der erste Name etwas häufiger vor als der letzte.

Die Verzerrung ist klein genug, dass niemand sie bemerkt, und genau deshalb überlebt sie in den meisten Implementierungen.

Der korrekte Ansatz ist Rejection Sampling: Ziehen, und wenn das Ergebnis in den unvollständigen letzten Abschnitt fällt, verwerfen und erneut ziehen. Die Verteilung wird exakt gleichverteilt, sodass jeder Eintrag eine 1/N-Chance hat — auch bei einer Ziehung mit 40 Namen, bei der eine Gleitkomma-Implementierung dem ersten Namen eine minimal höhere Wahrscheinlichkeit gibt.

Dieselbe Technik erscheint im Kurz-ID-Generator hier, wo die Annahmerate 252/256 beträgt und die resultierende Verzerrung etwa zwei zu zehn Millionen ist. Klein genug, um irrelevant zu sein, und klein genug, dass eine nachlässige Implementierung unbemerkt geblieben wäre — genau deshalb lohnt es sich, sie zu messen.

Drei menschliche Fehler, die nicht dem Tool zuzurechnen sind

Spielerfehlschluss. Nach fünfmal Kopf in Folge fühlt sich Zahl fällig an. Jede Ziehung ist unabhängig. Die Münze erinnert sich nicht daran, unfair gewesen zu sein, und die korrekte Wahrscheinlichkeit nach fünfmal Kopf ist weiterhin exakt 1/6 pro Seite.

Cluster-Illusion. Serien in zufälligen Daten wirken gemustert, weil Sie nach ihnen suchen. Drei identische Ergebnisse in Folge kommen weit häufiger vor, als die Intuition vermuten lässt. Und wirklich zufällige Daten sehen über kurze Läufe klumpig aus — eine Sequenz, die vollkommen gleichmäßig aussieht, ist eher erfunden als echt.

Geburtstagsparadoxon. In einer Gruppe von 23 Personen teilen wahrscheinlich zwei einen Geburtstag. Das ist Arithmetik, nicht Psychologie, aber es veranschaulicht, warum Menschen so schlecht darin sind, Zufälligkeit einzuschätzen: Die Einzelwahrscheinlichkeiten sind winzig, und sie multiplizieren sich.

Der gemeinsame Faden ist, dass eine einzelne Beobachtung nichts beweist, in keine der beiden Richtungen. Eine Ziehung, die seltsam aussah, ist genauso wenig aussagekräftig wie eine, die ordentlich aussah.

Die zwei Fehler, die in der Praxis am meisten zählen

Nachdem wir den Mechanismus nachvollzogen haben, lohnt es sich zu benennen, was tatsächlich schiefgeht, wenn eine Auswahl bestritten wird — und keiner dieser Punkte betrifft die Quelle.

Die Bedienperson hat das Ergebnis überschrieben. Neu würfeln, per Hand korrigieren, einen abwesenden Namen mitten in der Ziehung überspringen. Ein perfekter Generator und ein geändertes Ergebnis sind immer noch ein geändertes Ergebnis, und es ist für jeden sichtbar, der zugesehen hat.

Der Pool war nicht der veröffentlichte Pool. Einen Namen hinzuzufügen oder still einen auszuschließen, verändert die Auswahl unabhängig vom Algorithmus.

Beides sind Prozessfehler, und beides verhindert eine aufgezeichnete Ziehung. Deshalb ist eine Aufzeichnung mit der Teilnehmerliste im Bild mehr wert als jede technische Eigenschaft: Sie schließt beides aus.

Wo dieses Maß an Sorgfalt gerechtfertigt ist

Für die Wahl eines Mittagessens spielt nichts davon eine Rolle. Jeder Generator erzeugt ein akzeptables Mittagessen.

Es wird tragend, wenn es einen Einsatz, einen Ruf oder eine rechtliche Dimension gibt:

• Preisziehungen und Wettbewerbe. Ein überprüfbares Ergebnis ist der Punkt
• Mitarbeiter- oder Aufgabenzuweisung. Menschen werden den Prozess prüfen
• Wissenschaftliche und klinische Randomisierung. Der Standard des Feldes ist dokumentierte, mit Startwert versehene, reproduzierbare Zufälligkeit
• Regulatorische und prüfungsbezogene Kontexte. Dokumentierte Zufälligkeit ist häufig eine Anforderung, keine Vorliebe

Die Anforderungen in all diesen Fällen sind dieselben vier, und sie sind kurz: Der Pool ist fest und veröffentlicht, die Gewichte sind veröffentlicht, falls es welche gibt, die Quelle ist nicht vorhersehbar, und das Ergebnis wird mit sichtbarem Pool aufgezeichnet.

Wie Sie es selbst prüfen können

Sie können einen CSPRNG nicht in einem Browser-Tab prüfen, aber Sie können über den Mechanismus nachdenken, und das reicht.

Fragen Sie, was die Quelle ist. Wenn die Antwort „eine Zufallsfunktion“ lautet, fragen Sie, ob es die vorhersehbare ist. crypto.getRandomValues() ist eine konkrete, überprüfbare Antwort.

Fragen Sie, wie die Gleichverteilung erreicht wird. Wenn die Antwort das Abbilden eines Gleitkommawerts auf einen Bereich beinhaltet, ohne Rejection Sampling zu erwähnen, ist die Zuordnung wahrscheinlich verzerrt. Geringfügig, aber messbar.

Fragen Sie, was die Bedienperson hätte ändern können. Wenn nichts, ist das Ergebnis verteidigbar. Wenn ein Name übersprungen oder die Ziehung wiederholt werden könnte, ist es das nicht — unabhängig von der Quelle.

Die fairness page behandelt die Implementierung auf dieser Seite ausführlicher. Es lohnt sich, sie einmal zu lesen, wenn Sie ein Tool für eine Entscheidung wählen, die hinterfragt wird.