Arc4random Modulo voreingenommen

Question

Nach this documentation,

arc4random_uniform() über Konstruktionen wie arc4random() % upper_bound empfohlen, da es „Modulo-bias“ vermeidet, wenn die obere Grenze nicht eine Zweierpotenz ist.

Wie schlimm ist die Verzerrung? Wenn ich zum Beispiel Zufallszahlen mit einer Obergrenze von 6 erzeuge, was ist der Unterschied zwischen der Verwendung von arc4random mit % und arc4random_uniform()?

Answer 1

arc4random() gibt eine vorzeichenlose 32-Bit-Ganzzahl, das heißt, die Werte zwischen 0 und 2^32-1 = 4 294 967 295.

Nun werden die Bias ergibt sich aus der Tatsache, dass die mehreren Subintervallen erstellt mit modulo passen nicht genau in den zufälligen Ausgabebereich. Lassen Sie uns vorstellen, ein Zufallsgenerator, der Zahlen von 0 bis 198 einschließlich erstellt. Sie wollen Zahlen von 0 bis 99, also berechnen Sie random()% 100, wodurch man 0 bis 99:

0% 100 = 0
99% 100 = 99
100% 100 = 0
198% 100 = 98

Sie sehen, dass 99 die einzige Zahl, die zweimal in einem Durchlauf auftreten kann nur einmal während alle andere auftreten können. Das bedeutet, dass die Wahrscheinlichkeit für 99 genau halbiert wird, was auch der schlechteste Fall in einem Bias ist, bei dem mindestens zwei Subintervalle beteiligt sind.
Da alle Zweierpotenzen kleiner als das Intervallintervall gut in das 2^32 Intervall passen, verschwindet die Verzerrung in diesem Fall.

Die Implikationen sind, dass je kleiner das Ergebnis mit Modulo und die höhere der zufällige Ausgangsbereich, desto kleiner die Vorspannung. In Ihrem Beispiel ist 6 Ihre obere Grenze (ich nehme an, 0 ist die untere Grenze), so dass Sie% 7 verwenden, was dazu führt, dass 0-3 613 566 757 mal auftritt, während 4-6 613 566 756 mal auftritt.
Also 0-3 ist 613 566 757/613 566 756 = 1,0000000016298 mal wahrscheinlicher als 4-6.

Während es scheint einfach zu entlassen, einige Experimente (vor allem Monte-Carlo Experimente) waren genau deshalb fehlerhaft, weil diese scheinbar unglaublich kleine Unterschiede ziemlich wichtig waren.

Noch schlimmer ist der Bias, wenn der gewünschte Ausgabebereich größer als der zufällige Zielbereich ist. Bitte lesen Sie die Fisher-Yates shuffle Eintrag weil viele Poker-Websites auf die harte Weise, dass normale lineare congruential Zufallsgeneratoren und schlechte schlurfenden Algorithmen gelernt führte zu unmöglich oder sehr wahrscheinlich Decks oder noch schlimmer, vorhersehbar Decks.