Naar de inhoud
OneKitly

Schudden is moeilijker dan het lijkt: een miljoen keer de schudbeurt van één regel

Gepubliceerd op 11-6-2025 · 13 min leestijd · Dagelijkse calculators

Lena Hoffmann

Lena Hoffmann — Redacteur wetenschap en onderwijs bij OneKitly

Wiskunde · Natuurkunde

Getoetst aan 4 bronnen

Profiel bekijken →
Kort gezegd

Een rij sorteren met een toevallige vergelijkingsfunctie schudt haar niet. Laat een miljoen schudbeurten van de vier items A, B, C, D door `array.sort(() => Math.random() - 0.5)` lopen en elk van de vierentwintig mogelijke ordeningen zou ongeveer 41.667 keer moeten opduiken. Dat doen ze niet. Op Node 26.3.0 (V8 14.6) kwam de identieke ordening ABCD 62.485 keer terug en DBCA maar 30.998 keer — een verhouding van 2,02 op 1, en een chikwadraat van 125.397 bij 23 vrijheidsgraden tegen een kritieke waarde van 27,32 bij 5%. De structuur is geen ruis: precies acht van de vierentwintig ordeningen landen op kans 1/16 en de andere zestien op 1/32, een model dat vier miljoen verdere uitvoeringen past met een chikwadraat van 19,7. Diezelfde miljoen door Fisher-Yates gaf een chikwadraat van 10,3, ruimschoots binnen het toeval. De oorzaak is dat een vergelijkingsfunctie die een toevallig teken teruggeeft, geen consistente ordening is, dus hangt de uitvoer af van de binnenkant van het sorteeralgoritme — en dat maakt de vertekening eigen aan de engine en aan de versie in plaats van alleen maar klein. Fisher-Yates is drie regels, exact voor elke rijlengte, en heeft die afhankelijkheid niet. Gebruik het, trek de index om te verwisselen inclusief, en wijs de kortere weg via modulo af wanneer je een toevallig geheel getal op een bereik afbeeldt.

Advertentie

De schudbeurt die iedereen schrijft — sorteren met een toevallige vergelijkingsfunctie — is vertekend, en niet een beetje. Een miljoen gemeten uitvoeringen laten zien dat acht van de vierentwintig ordeningen twee keer zo vaak opduiken als de andere zestien.

Een miljoen schudbeurten van vier items

Vier items hebben vierentwintig ordeningen. Dat is klein genoeg om volledig te tellen, en juist daarom is het het goede proefgeval: laat een schudbeurt een miljoen keer lopen, houd bij hoe vaak elk van de vierentwintig eruit komt, en een eerlijke schudbeurt moet in elke bak ruwweg 41.667 zetten. Alles wat sommige ordeningen stelselmatig begunstigt, duikt op als een bult, en één getal — het chikwadraat — maakt van de hele tabel één oordeel. Bij 23 vrijheidsgraden scoort een eerlijke methode rond de 23, en alles boven 27,32 zou door toeval alleen in minder dan 5% van de gevallen gebeuren.

De regel van één scoorde 125.397. Niet 30, niet 300 — vijfduizend keer de drempel. De meest voorkomende ordening, BADC, kwam 62.810 keer op; de zeldzaamste, DBCA, 30.998 keer. De oorspronkelijke ordening ABCD bleef 62.485 keer heel, de helft vaker dan het zou moeten. Diezelfde miljoen door een correct geschreven Fisher-Yates liet 10,3 zien, en dat is hoe een eerlijke methode eruitziet: de uiterste tellingen waren 41.434 en 41.879, een spreiding van ongeveer 1%. De test naar vijf items oprekken maakte het gat nog groter — 229.683 tegen 89,0 — want elk extra element geeft het sorteeralgoritme nog een beslissing om slecht te nemen.

Advertentie

Geen vierentwintig kansen — twee

De tellingen liggen niet verspreid. Gesorteerd vallen ze in twee strakke clusters: acht ordeningen rond 62.500 en zestien rond 31.250. Dat is precies 1/16 en 1/32 van een miljoen, en de rekensom sluit — 8 × (1/16) + 16 × (1/32) = 1. Vier miljoen verdere uitvoeringen toetsten die hypothese rechtstreeks en leverden een chikwadraat van 19,7 bij 23 vrijheidsgraden op, en dat is een goede pasvorm. De schudbeurt van één regel op deze engine is dus niet ongeveer uniform met een wiebel; het is een verdeling met twee waarden waarin de helft van je kansmassa in een derde van de uitkomsten is gepropt.

De acht begunstigde ordeningen delen een eigenschap die het opmerken waard is: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC en DBAC houden C allemaal buiten de eerste twee posities. Dat is geen mystiek, het is het sorteeralgoritme dat erdoorheen lekt. Een rij van vier elementen is kort, dus verlaat V8 nooit zijn pad van binaire invoeging; de vergelijkingsfunctie wordt gemiddeld 4,5 keer aangeroepen, en 4,5 muntworpen kunnen onmogelijk 24 even waarschijnlijke uitkomsten voortbrengen, want 24 deelt geen enkele macht van twee. De vertekening zit in de vorm van de beslissingsboom gebakken nog voordat er toeval bij komt kijken.

De vertekening hoort bij de engine en niet bij de taal

ECMA-262 eist dat de vergelijkingsfunctie die aan sort wordt doorgegeven een consistente vergelijkingsfunctie is: ze moet transitief zijn, ze moet antisymmetrisch zijn, en ze moet voor hetzelfde paar elke keer hetzelfde antwoord geven. Een vergelijkingsfunctie die op Math.random is gebouwd, breekt alle drie binnen één aanroep. Het antwoord van de specificatie is niet om vast te leggen wat er dan gebeurt; het is om te zeggen dat als de vergelijkingsfunctie niet consistent is, de uitkomst van het sorteren door de implementatie wordt bepaald. Die ene zin is het hele verhaal. Je hebt geen schudbeurt met ongewone statistiek geschreven — je hebt een programma geschreven waarvan de standaard weigert de uitvoer vast te leggen.

Het praktische gevolg is dat deze tellingen een meting van één engine in één versie zijn en geen universele constante. V8 heeft zijn sortering meer dan eens gewijzigd; een uitvoering op een andere engine, of op dezelfde engine na een upgrade, levert een andere bultige verdeling op, en een rij die lang genoeg is om het samenvoegpad te raken levert er weer een andere op. Niets in de standaard verbiedt dat, en niets waarschuwt je wanneer het gebeurt. Een schudbeurt waarvan de statistische eigenschappen bewegen wanneer de runtime een patch krijgt, is geen schudbeurt die je kunt testen.

Fisher-Yates, en de off-by-one die het verpest

Het juiste algoritme — algoritme P van Knuth — loopt de rij van de laatste index naar de tweede af, en trekt op elke positie i een toevallige index j uniform van 0 tot en met i, en verwisselt dan de posities i en j. Drie details dragen het hele bewijs. De lus daalt. De trekking omvat i zelf, dus mag een element blijven waar het is. En het bereik krimpt elke doorloop met één, dus is het aantal mogelijke uitvoeringspaden n × (n−1) × … × 2 = n!, en dat is precies het aantal permutaties. Een bijectie tussen uitvoeringspaden en uitkomsten is wat uniformiteit betekent, en ze geldt voor elke n en niet alleen voor de n's die je hebt getest.

Verander één teken en het breekt. De gebruikelijke variant loopt de rij omhoog af en trekt j elke keer uit de hele rij, wat toevalliger voelt en het niet is. Die versie heeft n^n uitvoeringspaden, en n^n is voor n boven 2 nooit een veelvoud van n!, dus moeten sommige permutaties op meer manieren bereikbaar zijn dan andere. Gemeten op diezelfde miljoen uitvoeringen scoorde ze 29.913 — duizend keer de drempel, met de meest voorkomende ordening op 58.698 en de zeldzaamste op 31.233. Het is de gevaarlijkste van de twee fouten, juist omdat ze op de leerboekversie lijkt en elke blik met het blote oog doorstaat.

Modulovertekening: de tweede manier om een schudbeurt te buigen

Fisher-Yates heeft een uniform geheel getal in een bereik nodig, en de voor de hand liggende manier om er een uit een toevallige 32-bitswaarde te halen is haar modulo de bereikgrootte te nemen. Dat is alleen uniform wanneer het bereik 2^32 precies deelt. Dat doet het meestal niet: 2^32 modulo 52 is 48, dus krijgen 48 van de 52 uitkomsten één bronwaarde meer dan de andere vier. Bij 32 bits is het overschot ongeveer een miljoenste procent en zal niemand het ooit zien. Krimp de bron tot één byte en dezelfde rekenkunde wordt bruut: 256 modulo 52 is opnieuw 48, maar nu krijgen 48 uitkomsten 5 bronwaarden en 4 maar 4 — een overschot van 25%, zichtbaar in een paar duizend trekkingen.

De oplossing is de verwerpingsmethode en ze kost bijna niets. Bereken het grootste veelvoud van het bereik dat in je bron past — voor een trekking van 32 bits en een bereik van 52 is dat 2^32 min 48 — trek opnieuw zodra de waarde erboven landt, en neem de modulo alleen van aanvaarde waarden. Het verwerpingsgebied is 48 waarden uit 4.294.967.296, dus is het verwachte aantal extra trekkingen ongeveer één op negentig miljoen. Je betaalt één vergelijking per aanroep en koopt exacte uniformiteit, en dat is de beste ruil in dit hele artikel.

Math.random is geen kaartenschudder

Zelfs een perfecte Fisher-Yates wordt begrensd door de generator eronder. Een spel van 52 kaarten heeft 52! ordeningen, en dat is 8,07 × 10^67, ofwel ongeveer 2^225,6. De generator achter Math.random in V8 draagt 128 bits interne toestand, dus kan hij ten hoogste 2^128 ≈ 3,4 × 10^38 kaartordeningen bereiken — een fractie van 4,2 × 10^-30 van het totaal. De overgrote meerderheid van de schudbeurten van een standaardspel is simpelweg niet voort te brengen, hoe vaak je hem ook aanroept. Dat is een hard wiskundig plafond en geen gebrek in de uitvoering, en het geldt voor elke pseudotoevalsgenerator met minder toestand dan de ruimte die hij moet dekken.

Twee verdere eigenschappen doen in de praktijk ter zake. Math.random laat zich geen startwaarde geven en is niet herhaalbaar: de specificatie biedt geen manier om een beginpunt vast te leggen, en ze eist uitdrukkelijk dat verschillende realms verschillende reeksen voortbrengen, dus kan een fout die je één keer zag niet worden nagespeeld. En hij is niet onvoorspelbaar in cryptografische zin — wie genoeg uitvoer ziet, kan de toestand reconstrueren en de rest voorspellen. Zou iemand erbij kunnen winnen door je schudbeurt te raden — een verloting, een trekking met een prijs, een beveiligingstoken, wat er ook voor publiek wordt geschud — gebruik dan crypto.getRandomValues, met de verwerpingsmethode erbovenop. Is de schudbeurt een plaatsindeling of een oefentoets, dan is Math.random met een correcte Fisher-Yates volkomen in orde.

Verhouding
Een miljoen schudbeurten van de vier items A, B, C, D met drie methoden, permutatie voor permutatie geteld (Node 26.3.0, V8 14.6). Bij een eerlijke schudbeurt zou elk van de 24 ordeningen ongeveer 41.667 keer moeten voorkomen.
MethodeZeldzaamste ordeningMeest voorkomende ordeningVerhoudingChikwadraat, 23 vgOordeel bij 5% (kritieke waarde 27,32)
sort(() => Math.random() - 0.5)30.998 (DBCA)62.810 (BADC)2,026125.397,2Vertekend, zonder enige twijfel
Fisher-Yates (aflopende lus, inclusieve index)41.434 (ABDC)41.879 (BDAC)1,01110,3Niet van uniform te onderscheiden
Fisher-Yates met de off-by-one (index uit de hele rij getrokken)31.233 (DBCA)58.698 (BADC)1,87929.913,6Vertekend, en het lijkt juist
Wat een eerlijke schudbeurt zou gevenongeveer 41.667ongeveer 41.6671,000ongeveer 23De referentieregel
Regels in willekeurige ordeSchud tekstregels met een keuze uit meerdere algoritmen, opschoonopties en een optionele herhaalbare seed.Probeer de tool →
Advertentie

Veelgestelde vragen

Is sorteren met een toevallige vergelijkingsfunctie altijd vertekend, of alleen in sommige browsers?
Altijd vertekend, maar overal anders vertekend. De standaard eist een consistente vergelijkingsfunctie en verklaart de uitkomst door de implementatie bepaald wanneer hij er geen krijgt, dus brengt elke engine — en elke versie van elke engine — zijn eigen bultige verdeling voort. Op Node 26.3.0 valt het geval met vier items terug op maar twee kansen, 1/16 voor acht ordeningen en 1/32 voor de andere zestien, wat een test van vier miljoen uitvoeringen bevestigt met een chikwadraat van 19,7 bij 23 vrijheidsgraden. Een andere engine geeft je die exacte getallen niet; hij geeft je andere verkeerde getallen. Dat is slechter dan een bekende, vaste vertekening, want er is niets stabiels om tegen te testen en een upgrade van de runtime kan de statistiek van je trekking veranderen zonder dat er een regel van je code verandert.
Hoe schrijf ik Fisher-Yates zo dat het werkelijk juist is?
Begin bij de laatste index en loop af naar index 1. Trek op elke positie i de index j uniform van 0 tot en met i, en verwissel dan de elementen op i en j. Drie dingen moeten tegelijk goed zijn: de lus daalt, de trekking omvat i zelf, en het bereik krimpt elke doorloop met één. Krijg je alle drie goed, dan is het aantal uitvoeringspaden precies n-faculteit, één per permutatie, en dat is wat de uitvoer uniform maakt voor elke rijlengte in plaats van voor de lengtes die je toevallig hebt getest. De variant die omhoog loopt en j elke keer uit de hele rij trekt, is de klassieke fout — die heeft n tot de macht n paden, en dat is boven n = 2 nooit een veelvoud van n-faculteit, en ze mat een chikwadraat van 29.913 op de test met vier items waar een eerlijke schudbeurt ongeveer 23 scoort.
Heb ik crypto.getRandomValues nodig, of is Math.random goed genoeg?
De toets is of iemand erbij zou kunnen winnen door de uitkomst te voorspellen. Vragen van een quiz schudden, een klas indelen, de volgorde van oefenopgaven toevallig maken: Math.random binnen een correcte Fisher-Yates is in orde, en het verschil zal nooit opvallen. Een prijs trekken, een steekproef voor een controle kiezen, iets voortbrengen dat zich als een token gedraagt: gebruik crypto.getRandomValues, want Math.random is een pseudotoevalsgenerator waarvan de interne toestand uit een bescheiden reeks uitvoer te reconstrueren is, waarna elke toekomstige waarde voorspelbaar is. Er is een tweede, stillere reden. Een spel van 52 kaarten heeft ongeveer 2^225,6 ordeningen en de generator van V8 draagt 128 bits toestand, dus kan hij er ten hoogste één op 10^30 bereiken. Dat plafond is inherent aan de grootte van de toestand en niet aan de kwaliteit van het algoritme.
Wat is modulovertekening precies, en wanneer doet ze ter zake?
Het is wat er gebeurt wanneer je een bereik perst dat je bron niet deelt. Neem een toevallige 32-bitswaarde en reduceer haar modulo 52 en je krijgt een getal van 0 tot 51, maar 2^32 gedeeld door 52 laat een rest van 48, dus hebben 48 van die uitkomsten één bronwaarde meer die erop afbeeldt dan de overige vier. Bij 32 bits is het overschot rond een miljoenste procent — werkelijk verwaarloosbaar. Dezelfde rekenkunde op een bron van 8 bits is een ander beest: 256 modulo 52 is ook 48, maar nu krijgen de begunstigde uitkomsten 5 bronwaarden en de andere maar 4, een overschot van 25% dat een paar duizend trekkingen blootlegt. De oplossing is de verwerpingsmethode: verwerp elke trekking op of boven het grootste veelvoud van het bereik dat in je bron past, wat voor 32 bits en een bereik van 52 48 waarden uit 4,29 miljard verwerpt, ongeveer één trekking op negentig miljoen.
Hoe test ik mijn eigen schudbeurt zonder achtergrond in statistiek?
Krimp het probleem tot je alles kunt tellen. Neem een rij van vier items, schud haar een miljoen keer, en houd bij hoe vaak elk van de vierentwintig ordeningen voorkomt — een woordenboek met de samengevoegde tekenreeks als sleutel is genoeg. Kijk dan naar twee getallen: de grootste telling gedeeld door de kleinste, en de telling van de oorspronkelijke ongeschudde ordening. Een eerlijke schudbeurt geeft bij die steekproefgrootte een verhouding rond 1,01 en laat de oorspronkelijke ordening op ruwweg 1 op 24. In de metingen hier gaf Fisher-Yates 1,011 en de sortering van één regel 2,026, met de onaangeroerde ordening die 50% vaker voorkwam dan het zou moeten. Je hebt het chikwadraat niet nodig om dat gat te zien; het chikwadraat vertelt je alleen hoe onmogelijk het is, en 125.397 tegen een drempel van 27,32 is ongeveer zo onmogelijk als metingen worden.

Artikelen die je misschien interesseren

Alle gidsen →
GidsMensen in eerlijke groepen verdelen: toevallig en eerlijk zijn niet dezelfde eis23 mensen delen niet door vier, en een uniform toevallige verdeling kan één groep alle sterke spelers geven. Hier zijn de rekenkunde van de rest, de gemeten prijs van puur toeval, en de gestratificeerde oplossing.GidsToernooischema's: byes, plaatsingen en waarom de getallen machten van twee moeten zijnEen knock-outschema halveert zijn veld elke ronde, dus sluit het alleen op een macht van twee. Het aantal byes, het aantal ronden, de plaatsingsvolgorde en het totale aantal wedstrijden volgen allemaal uit dat ene feit — en elk ervan is een afleiding van één regel.HandleidingHoe je een naam willekeurig trekt — zonder dat iemand het resultaat betwistEen eerlijke trekking vraagt meer dan een willekeurig getal: gelijke kans, geen vertekende methode, en een uitslag die een ander kan controleren. Zo doe je dat.UitlegKansen op pokerhanden, afgeleid in plaats van uit het hoofd geleerdElke kans op een hand van vijf kaarten is een telargument over 2.598.960 handen, en elk ervan past op één regel. Hier zijn alle negen, met de controle die ze bewijst: de tellingen moeten precies op C(52,5) uitkomen.UitlegThe Sum of the Implied Probabilities Is Never One HundredTwo sides both priced at -110 imply 52.4 % each. That adds to 104.8 %, and the 4.8 points that should not exist are the margin — visible the moment you convert the odds.UitlegTest Card Numbers: What the Luhn Algorithm Is Actually For, and What It Cannot Tell YouLuhn is a checksum for catching typos, patented in 1960, and that is its entire job. A number that passes it tells you nothing about any account. For testing a payment integration you need your processor's published numbers, not a generated one.

Vergelijkbare tools

Bronnen

Een fout in dit artikel gezien?