Eliminierung der Modulo-Bias: Wie wird es in der Funktion arc4random_uniform() erreicht?

Question

Modulo-Bias ist ein Problem, das entsteht, wenn man naiv die Modulo-Operation verwendet, um Pseudozufallszahlen kleiner als eine gegebene "obere Grenze" zu erhalten.

Daher verwende ich als C-Programmierer eine modifizierte Version der arc4random_uniform()-Funktion, um gleichmäßig verteilte Pseudozufallszahlen zu erzeugen.

Das Problem ist, ich verstehe nicht, wie die Funktion mathematisch funktioniert.

Dies ist die erläuternde Kommentar der Funktion, durch einen Link zur vollständigen Quellcode gefolgt:

/* 
* Calculate a uniformly distributed random number less than upper_bound 
* avoiding "modulo bias". 
* 
* Uniformity is achieved by generating new random numbers until the one 
* returned is outside the range [0, 2**32 % upper_bound). This 
* guarantees the selected random number will be inside 
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 
* after reduction modulo upper_bound. 
*/ 

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/x-cvsweb-markup

Aus dem Kommentar oben wir definieren:

• [2^32 % upper_bound, 2^32) - Intervall A
• [0, upper_bound) - Intervall B

Um zu arbeiten, setzt die Funktion auf der Tatsache, dass Intervall A Karten B. Intervall

Meine Frage ist: mathematisch, wie die Zahlen im Intervall im Intervall Eine Karte kommt gleichmäßig auf denjenigen B? Und gibt es einen Beweis dafür?

Answer 1

Manchmal hilft es, mit einem leicht verständlichen Beispiel zu beginnen und dann von dort zu verallgemeinern. Um die Dinge einfach zu halten, stellen wir uns vor, dass arc4random eine uint8_t anstelle einer uint32_t zurückgibt, so dass die Ausgabe von arc4random eine Zahl im Intervall [0,256) ist. Und lassen Sie uns eine upper_bound von 7.

Hinweis wählen, dass 7 nicht gleichmäßig teilen sich in 256

256 = 7 * 36 + 4 

Das bedeutet, dass ganz naiv die Modulo-Operation unter Verwendung von Pseudo-Zufallszahlen erhalten kleiner als 7 in der folgenden Wahrscheinlichkeitsverteilung führen würde

37/256 for outcomes 0,1,2,3 
36/256 for outcomes 4,5,6 

das ist, was als Modulo-Bias bekannt ist, Ergebnisse 0,1,2,3 eher als Ergebnisse 4,5,6.

Um Modulo-Bias zu vermeiden, könnten wir einfach die Werte 252,253,254,255 ablehnen und eine neue Zahl generieren, bis das Ergebnis im Intervall [0,252) liegt. Alle Nummern im Intervall [0,252) haben die gleiche Wahrscheinlichkeit (die Ablehnung höherer Zahlen wirkt sich nicht auf die Verteilung der niedrigeren Zahlen aus). Und da 7 teilt gleichmäßig in 252, ist die sich ergebende Wahrscheinlichkeitsverteilung uniform

36/252 for outcomes 0,1,2,3,4,5,6,7 

Das ist im Wesentlichen, was arc4random_uniform der Fall ist, außer dass arc4random_uniform Spuck Zahlen am unteren Rand des Bereichs.Insbesondere wäre Intervall A

sein

[2^8 % 7, 2^8) which is [4, 256) 

Nach einer Anzahl Erzeugen (nennen wir es N) im Intervall [4.256) Die endgültige Berechnung wird

outcome = N % 7 

Es gibt 252 Zahlen im Intervall [4.256), und da 252 ein Vielfaches von 7 ist, hat jedes Ergebnis im Intervall [0,7] die gleiche Wahrscheinlichkeit.

---

Das ist, wie arc4random_uniform funktioniert, es lehnt/Wiederholungen auf einem kleinen Bereich von Zahlen, und die Anzahl der Zahlen in den verbleibenden Bereich ist ein Vielfaches der upper_bound. (Da der obere_Bereich typischerweise eine kleine Anzahl im Vergleich zu 2^32 ist, ist die Wahrscheinlichkeit, mehrere Wiederholungen für ein einzelnes Ergebnis zu haben, ziemlich gering.)

Aber interessiert Sie wirklich die Modulo-Verzerrung? In den meisten Fällen lautet die Antwort "Nein". Betrachten wir unser Beispiel mit einem oberen von 7. Die Wahrscheinlichkeitsverteilung für die naive modulo Umsetzung gebunden ist

613566757/4294967296 for outcomes 0,1,2,3 
613566756/4294967296 for outcomes 4,5,6 

, die eine Modulo-Vorspannung von weniger als 0,0000002% beträgt.

Sie haben also die Wahl: Entweder geben Sie einen winzigen Teil der Zeit für Wiederholungen aus, um eine perfekte Verteilung zu erhalten, oder Sie akzeptieren einen winzigen Fehler in der Wahrscheinlichkeitsverteilung, um Wiederholungen zu vermeiden.