Mischen ist schwerer, als es aussieht: eine Million Durchläufe des Einzeiler-Mischens

Eine Million Mischvorgänge mit vier Elementen

Vier Elemente haben vierundzwanzig Reihenfolgen. Das ist klein genug, um vollständig auszuzählen, und genau deshalb der richtige Testfall: Lass ein Mischverfahren eine Million Mal laufen, zähle, wie oft jede der vierundzwanzig herauskommt, und faires Mischen muss in jedes Fach rund 41 667 legen. Alles, was einzelne Reihenfolgen systematisch bevorzugt, zeigt sich als Beule, und eine einzige Zahl — die Chi-Quadrat-Statistik — verdichtet die ganze Tabelle zu einem Urteil. Bei 23 Freiheitsgraden liegt ein faires Verfahren um 23, und alles über 27,32 träte rein zufällig in weniger als 5 % der Fälle auf.

Der Einzeiler erreichte 125 397. Nicht 30, nicht 300 — das Fünftausendfache der Schwelle. Die häufigste Reihenfolge, BADC, kam 62 810 Mal; die seltenste, DBCA, 30 998 Mal. Die Ausgangsreihenfolge ABCD überlebte 62 485 Mal unversehrt, anderthalbmal so oft wie vorgesehen. Dieselbe Million durch ein korrekt geschriebenes Fisher-Yates ergab 10,3 — so sieht ein faires Verfahren aus: Die Extremwerte lagen bei 41 434 und 41 879, eine Spanne von rund 1 %. Der Test mit fünf Elementen reißt die Lücke weiter auf — 229 683 gegen 89,0 —, denn jedes zusätzliche Element gibt dem Sortieralgorithmus eine Entscheidung mehr, die er falsch treffen kann.

Nicht vierundzwanzig Wahrscheinlichkeiten, sondern zwei

Die Zählungen streuen nicht. Sortiert fallen sie in zwei enge Cluster: acht Reihenfolgen um 62 500 und sechzehn um 31 250. Das sind genau 1/16 und 1/32 einer Million, und die Rechnung geht auf — 8 × (1/16) + 16 × (1/32) = 1. Weitere vier Millionen Durchläufe prüften diese Hypothese direkt und lieferten ein Chi-Quadrat von 19,7 bei 23 Freiheitsgraden, also eine gute Anpassung. Das Einzeiler-Mischen auf dieser Engine ist damit nicht näherungsweise gleichverteilt mit etwas Wackeln, sondern eine zweiwertige Verteilung, in der die halbe Wahrscheinlichkeitsmasse in ein Drittel der Ergebnisse gepresst ist.

Die acht bevorzugten Reihenfolgen teilen eine bemerkenswerte Eigenschaft: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC und DBAC halten C jeweils aus den ersten beiden Positionen heraus. Das ist keine Mystik, sondern der durchscheinende Sortieralgorithmus. Ein Vier-Element-Array ist kurz, also verlässt V8 seinen binären Einfügepfad nie; der Vergleicher wird im Mittel 4,5 Mal aufgerufen, und 4,5 Münzwürfe können unmöglich 24 gleich wahrscheinliche Ergebnisse erzeugen, denn 24 teilt keine Zweierpotenz. Die Verzerrung steckt in der Form des Entscheidungsbaums, noch bevor Zufall ins Spiel kommt.

Die Verzerrung gehört zur Engine, nicht zur Sprache

ECMA-262 verlangt, dass die an sort übergebene Vergleichsfunktion ein konsistenter Vergleicher ist: transitiv, antisymmetrisch, und für dasselbe Paar stets dieselbe Antwort liefernd. Ein auf Math.random gebauter Vergleicher bricht alle drei Bedingungen in einem einzigen Aufruf. Die Spezifikation reagiert nicht damit, das Verhalten festzulegen, sondern damit, das Sortierergebnis bei inkonsistentem Vergleicher als implementierungsabhängig zu erklären. Dieser eine Satz ist die ganze Geschichte. Du hast kein Mischverfahren mit ungewöhnlicher Statistik geschrieben, sondern ein Programm, dessen Ausgabe der Standard zu spezifizieren ablehnt.

Praktisch heißt das: Diese Zählungen messen eine Engine in einer Version, keine universelle Konstante. V8 hat seine Sortierung mehr als einmal umgestellt; ein Lauf auf einer anderen Engine oder auf derselben nach einem Update erzeugt eine andere buckelige Verteilung, und ein Array, das lang genug für den Merge-Pfad ist, wieder eine andere. Nichts im Standard verbietet das, und nichts warnt dich, wenn es passiert. Ein Mischverfahren, dessen statistische Eigenschaften sich mit einem Runtime-Patch verschieben, ist kein testbares Mischverfahren.

Fisher-Yates und der Indexfehler, der es ruiniert

Der korrekte Algorithmus — Knuths Algorithmus P — läuft das Array vom letzten Index bis zum zweiten hinab und zieht an jeder Position i einen Index j gleichverteilt aus 0 bis einschließlich i, dann werden i und j getauscht. Drei Details tragen den ganzen Beweis. Die Schleife läuft abwärts. Die Ziehung schließt i selbst ein, ein Element darf also stehen bleiben. Und der Bereich schrumpft je Durchlauf um eins, sodass die Zahl der Ausführungspfade n × (n−1) × … × 2 = n! beträgt, genau die Zahl der Permutationen. Eine Bijektion zwischen Ausführungspfaden und Ergebnissen ist genau das, was Gleichverteilung bedeutet, und sie gilt für jedes n, nicht nur für die getesteten.

Ändere ein Zeichen, und es bricht. Die gängige Variante läuft das Array aufwärts und zieht j jedes Mal aus dem ganzen Array, was zufälliger wirkt und es nicht ist. Diese Version hat n^n Ausführungspfade, und n^n ist für n über 2 nie ein Vielfaches von n! — manche Permutationen müssen also auf mehr Wegen erreichbar sein als andere. An derselben Million gemessen erreichte sie 29 913 — das Tausendfache der Schwelle, mit der häufigsten Reihenfolge bei 58 698 und der seltensten bei 31 233. Sie ist der gefährlichere der beiden Fehler, gerade weil sie wie die Lehrbuchfassung aussieht und jede Sichtprüfung besteht.

Modulo-Verzerrung: der zweite Weg, ein Mischen zu verbiegen

Fisher-Yates braucht eine gleichverteilte ganze Zahl in einem Bereich, und der naheliegende Weg dorthin aus einem zufälligen 32-Bit-Wert ist der Modulo der Bereichsgröße. Das ist nur gleichverteilt, wenn der Bereich 2^32 exakt teilt. Meist tut er das nicht: 2^32 modulo 52 ist 48, also erhalten 48 der 52 Ergebnisse ein Urbild mehr als die übrigen vier. Bei 32 Bit liegt der Überschuss bei etwa einem Millionstel Prozent, und niemand wird ihn je sehen. Verkleinere die Quelle auf ein einzelnes Byte, und dieselbe Rechnung wird brutal: 256 modulo 52 ist wieder 48, aber nun bekommen 48 Ergebnisse 5 Urbilder und 4 nur 4 — ein Überschuss von 25 %, sichtbar in wenigen tausend Ziehungen.

Die Lösung heißt Verwerfungsstichprobe und kostet fast nichts. Berechne das größte Vielfache des Bereichs, das in deine Quelle passt — bei einer 32-Bit-Ziehung und Bereich 52 ist das 2^32 minus 48 —, ziehe neu, sobald der Wert darüber liegt, und nimm den Modulo nur von akzeptierten Werten. Der Verwerfungsbereich umfasst 48 von 4 294 967 296 Werten, die erwartete Zahl zusätzlicher Ziehungen liegt also bei etwa eins zu neunzig Millionen. Du zahlst einen Vergleich pro Aufruf und kaufst exakte Gleichverteilung — der beste Tausch in diesem ganzen Artikel.

Math.random ist keine Kartenmischmaschine

Selbst ein perfektes Fisher-Yates ist durch den Generator darunter begrenzt. Ein 52-Karten-Deck hat 52! Reihenfolgen, also 8,07 × 10^67 oder etwa 2^225,6. Der Generator hinter Math.random in V8 trägt 128 Bit internen Zustand, kann also höchstens 2^128 ≈ 3,4 × 10^38 Deckreihenfolgen erreichen — ein Anteil von 4,2 × 10^-30 am Ganzen. Die überwältigende Mehrheit der Mischungen eines Standarddecks ist schlicht nicht erzeugbar, so oft du auch aufrufst. Das ist eine harte mathematische Decke, kein Implementierungsfehler, und sie gilt für jeden Pseudozufallsgenerator mit weniger Zustand als der Raum, den er abdecken soll.

Zwei weitere Eigenschaften zählen in der Praxis. Math.random ist weder mit einem Startwert versehbar noch reproduzierbar: Die Spezifikation bietet keinen Weg, einen Startpunkt festzulegen, und verlangt ausdrücklich, dass verschiedene Realms verschiedene Folgen erzeugen — ein einmal gesehener Fehler lässt sich also nicht nachspielen. Und sie ist im kryptografischen Sinn nicht unvorhersagbar: Wer genügend Ausgaben sieht, kann den Zustand rekonstruieren und den Rest vorhersagen. Wenn jemand daran gewinnen könnte, dein Mischen zu erraten — eine Tombola, eine Verlosung mit Preis, ein Sicherheitstoken, alles, was vor Publikum gemischt wird —, nimm crypto.getRandomValues, mit Verwerfungsstichprobe obendrauf. Geht es um einen Sitzplan oder ein Übungsquiz, ist Math.random mit korrektem Fisher-Yates völlig in Ordnung.

Häufige Fragen

Ist Sortieren mit einem Zufallsvergleicher immer verzerrt oder nur in manchen Browsern?

Immer verzerrt, aber überall anders verzerrt. Der Standard verlangt einen konsistenten Vergleicher und erklärt das Ergebnis für implementierungsabhängig, wenn er keinen bekommt — jede Engine und jede Version jeder Engine erzeugt also ihre eigene buckelige Verteilung. Auf Node 26.3.0 fällt der Vier-Element-Fall auf nur zwei Wahrscheinlichkeiten zusammen, 1/16 für acht Reihenfolgen und 1/32 für die übrigen sechzehn, was ein Test über vier Millionen Durchläufe mit einem Chi-Quadrat von 19,7 bei 23 Freiheitsgraden bestätigt. Eine andere Engine liefert nicht diese Zahlen, sondern andere falsche Zahlen. Das ist schlimmer als eine bekannte, feste Verzerrung, weil es nichts Stabiles zum Testen gibt und ein Runtime-Update die Statistik deiner Ziehung ändern kann, ohne dass sich eine Zeile Code ändert.

Wie schreibe ich Fisher-Yates so, dass es tatsächlich korrekt ist?

Beginne beim letzten Index und laufe hinab bis Index 1. Ziehe an jeder Position i ein j gleichverteilt aus 0 bis einschließlich i und tausche dann die Elemente an i und j. Drei Dinge müssen gleichzeitig stimmen: Die Schleife läuft abwärts, die Ziehung schließt i selbst ein, und der Bereich schrumpft je Durchlauf um eins. Stimmen alle drei, beträgt die Zahl der Ausführungspfade genau n Fakultät, einer je Permutation — und genau das macht die Ausgabe für jede Arraylänge gleichverteilt und nicht nur für die zufällig getesteten. Die Variante, die aufwärts läuft und j jedes Mal aus dem ganzen Array zieht, ist der klassische Fehler: Sie hat n hoch n Pfade, was oberhalb von n = 2 nie ein Vielfaches von n Fakultät ist, und sie erreichte im Vier-Element-Test ein Chi-Quadrat von 29 913, wo faires Mischen bei etwa 23 liegt.

Brauche ich crypto.getRandomValues, oder reicht Math.random?

Der Test lautet: Könnte jemand daran gewinnen, das Ergebnis vorherzusagen? Quizfragen mischen, eine Klasse setzen, die Reihenfolge von Übungsaufgaben zufällig machen: Math.random in einem korrekten Fisher-Yates genügt, und der Unterschied wird nie sichtbar. Einen Preis verlosen, eine Prüfstichprobe ziehen, irgendetwas erzeugen, das sich wie ein Token verhält: nimm crypto.getRandomValues, denn Math.random ist ein Pseudozufallsgenerator, dessen interner Zustand sich aus einer überschaubaren Folge von Ausgaben rekonstruieren lässt — danach ist jeder künftige Wert vorhersagbar. Es gibt einen zweiten, leiseren Grund. Ein 52-Karten-Deck hat rund 2^225,6 Reihenfolgen, und V8s Generator trägt 128 Bit Zustand, erreicht also höchstens eine Deckreihenfolge von 10^30. Diese Decke folgt aus der Zustandsgröße, nicht aus der Qualität des Algorithmus.

Was genau ist Modulo-Verzerrung, und wann fällt sie ins Gewicht?

Sie entsteht, wenn man einen Bereich presst, der die Quelle nicht teilt. Nimm einen zufälligen 32-Bit-Wert und reduziere ihn modulo 52: Du bekommst eine Zahl von 0 bis 51, aber 2^32 geteilt durch 52 lässt den Rest 48, also fallen auf 48 dieser Ergebnisse ein Quellwert mehr als auf die restlichen vier. Bei 32 Bit liegt der Überschuss bei etwa einem Millionstel Prozent — wirklich vernachlässigbar. Dieselbe Rechnung auf einer 8-Bit-Quelle ist ein anderes Tier: 256 modulo 52 ist ebenfalls 48, doch nun erhalten die bevorzugten Ergebnisse 5 Quellwerte und die übrigen nur 4 — ein Überschuss von 25 %, den wenige tausend Ziehungen sichtbar machen. Die Lösung ist die Verwerfungsstichprobe: Verwirf jede Ziehung ab dem größten Vielfachen des Bereichs, das in die Quelle passt; bei 32 Bit und Bereich 52 sind das 48 Werte von 4,29 Milliarden, also etwa eine Ziehung von neunzig Millionen.

Wie teste ich mein eigenes Mischverfahren ohne Statistikkenntnisse?

Verkleinere das Problem, bis du alles zählen kannst. Nimm ein Array aus vier Elementen, mische es eine Million Mal und führe Strichliste, wie oft jede der vierundzwanzig Reihenfolgen erscheint — ein Wörterbuch mit der zusammengefügten Zeichenkette als Schlüssel genügt. Sieh dann auf zwei Zahlen: den größten Zählwert geteilt durch den kleinsten, und den Zählwert der ursprünglichen, ungemischten Reihenfolge. Faires Mischen ergibt bei dieser Stichprobengröße ein Verhältnis nahe 1,01 und lässt die Ausgangsreihenfolge bei etwa 1 von 24. In den Messungen hier lieferte Fisher-Yates 1,011 und die Einzeiler-Sortierung 2,026, wobei die unveränderte Reihenfolge 50 % häufiger auftrat als vorgesehen. Für diese Lücke brauchst du kein Chi-Quadrat; das Chi-Quadrat sagt nur, wie unmöglich sie ist — und 125 397 gegen eine Schwelle von 27,32 ist ungefähr so unmöglich, wie Messungen werden.