Warum sagen die Leute, dass es bei Verwendung eines Zufallszahlengenerators eine Modulo-Verzerrung gibt?

277

Ich habe gesehen, dass diese Frage oft gestellt wurde, aber nie eine konkrete Antwort darauf gesehen. Ich werde hier eine veröffentlichen, die den Leuten hoffentlich helfen wird zu verstehen, warum genau "Modulo Bias" vorliegt, wenn ein Zufallszahlengenerator wie rand()in C ++ verwendet wird.

user1413793
quelle

Antworten:

394

Dies rand()gilt auch für einen Pseudozufallszahlengenerator, der eine natürliche Zahl zwischen 0 und wählt RAND_MAX, eine Konstante, die in definiert ist cstdlib(siehe diesen Artikel für eine allgemeine Übersicht überrand() ).

Was passiert nun, wenn Sie eine Zufallszahl zwischen 0 und 2 generieren möchten? Nehmen wir zur Erklärung an, es RAND_MAXist 10, und ich beschließe, durch Aufrufen eine Zufallszahl zwischen 0 und 2 zu generieren rand()%3. Erzeugt rand()%3jedoch nicht die Zahlen zwischen 0 und 2 mit gleicher Wahrscheinlichkeit!

Wenn rand()0, 3, 6 oder 9 zurückgegeben wird , rand()%3 == 0 . Daher ist P (0) = 4/11

Wenn rand()1, 4, 7 oder 10 zurückgegeben wird , rand()%3 == 1 . Daher ist P (1) = 4/11

Wenn rand()2, 5 oder 8 zurückgegeben wird , rand()%3 == 2 . Daher ist P (2) = 3/11

Dies erzeugt nicht die Zahlen zwischen 0 und 2 mit gleicher Wahrscheinlichkeit. Natürlich ist dies für kleine Bereiche möglicherweise nicht das größte Problem, aber für einen größeren Bereich kann dies die Verteilung verzerren und die kleineren Zahlen beeinflussen.

Wann wird also rand()%nmit gleicher Wahrscheinlichkeit ein Zahlenbereich von 0 bis n-1 zurückgegeben? Wann RAND_MAX%n == n - 1. In diesem Fall wird zusammen mit unserer früheren Annahme rand()eine Zahl zwischen 0 und 0 zurückgegebenRAND_MAX mit gleicher Wahrscheinlichkeit auch die Moduloklassen von n gleichmäßig verteilt sein.

Wie lösen wir dieses Problem? Eine grobe Methode besteht darin, so lange Zufallszahlen zu generieren, bis Sie eine Zahl in Ihrem gewünschten Bereich erhalten:

int x; 
do {
    x = rand();
} while (x >= n);

Dies ist jedoch für niedrige Werte von ineffizient n, da Sie nur die n/RAND_MAXChance haben, einen Wert in Ihrem Bereich zu erhalten, und Sie daher RAND_MAX/nAnrufe bei tätigen müssenrand() durchschnittlich .

Eine effizientere Formel Ansatz wäre, eine große Strecke mit einer Länge teilbar zu nehmen , indem n, wie RAND_MAX - RAND_MAX % n, halten Zufallszahlen zu erzeugen , bis Sie ein , dass liegt im Bereich, und dann den Modul nehmen:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

Für kleine Werte von nerfordert dies selten mehr als einen Aufruf von rand().


Zitierte Werke und weiterführende Literatur:


user1413793
quelle
6
Eine andere Art, über RAND_MAX%n == n - 1_ _ nachzudenken, ist (RAND_MAX + 1) % n == 0. Wenn ich Code lese, verstehe ich ihn eher % something == 0als „gleichmäßig teilbar“ als andere Berechnungsmethoden. Wenn Ihre C ++ - stdlib RAND_MAXden gleichen Wert wie hat INT_MAX, (RAND_MAX + 1)würde dies natürlich nicht funktionieren. Daher bleibt Marks Berechnung die sicherste Implementierung.
Slipp D. Thompson
sehr schöne Antwort!
Sayali Sonawane
Ich mag nicht picken, aber wenn das Ziel darin besteht, verschwendete Bits zu reduzieren, könnten wir dies geringfügig für die Randbedingung verbessern, bei der RAND_MAX (RM) nur 1 weniger ist, als durch N gleichermaßen teilbar zu sein. In diesem Szenario müssen keine Bits durch verschwendet werden X> = (RM - RM% N)), was für kleine Werte von N von geringem Wert ist, für große Werte von N jedoch von größerem Wert wird. Wie von Slipp D. Thompson erwähnt, gibt es eine Lösung, die nur funktioniert wenn INT_MAX (IM)> RAND_MAX, aber bricht, wenn sie gleich sind. Es gibt jedoch eine einfache Lösung dafür. Wir können die Berechnung X> = (RM - RM% N) wie folgt ändern:
Ben Personick
X> = RM - (((RM% N) + 1)% N)
Ben Personick
Ich habe eine zusätzliche Antwort veröffentlicht, in der das Problem ausführlich erläutert und die Beispielcodelösung angegeben wird.
Ben Personick
36

Die Auswahl eines Zufalls ist ein guter Weg, um die Verzerrung zu beseitigen.

Aktualisieren

Wir könnten den Code schnell machen, wenn wir nach einem x im Bereich suchen, der durch teilbar ist n.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

Die obige Schleife sollte sehr schnell sein, beispielsweise durchschnittlich 1 Iteration.

Nick Dandoulakis
quelle
2
Yuck :-P Konvertieren in ein Double, dann Multiplizieren mit MAX_UPPER_LIMIT / RAND_MAX ist viel sauberer und bietet eine bessere Leistung.
Boycy
22
@boycy: du hast den Punkt verpasst. Wenn die Anzahl der Werte, die zurückgegeben werden rand()können, kein Vielfaches von ist n, erhalten Sie bei allem, was Sie tun, unweigerlich eine "Modulo-Verzerrung", es sei denn, Sie verwerfen einige dieser Werte. user1413793 erklärt das gut (obwohl die in dieser Antwort vorgeschlagene Lösung wirklich glücklich ist).
TonyK
4
@ TonyK Ich entschuldige mich, ich habe den Punkt verpasst. Ich habe nicht gut genug nachgedacht und dachte, die Verzerrung würde nur bei Methoden gelten, die eine explizite Moduloperation verwenden. Danke, dass du mich repariert hast :-)
Boycy
Durch die Priorität des Operators RAND_MAX+1 - (RAND_MAX+1) % nfunktioniert die Arbeit korrekt, aber ich denke immer noch, dass sie RAND_MAX+1 - ((RAND_MAX+1) % n)aus Gründen der Klarheit geschrieben werden sollte.
Linus Arver
4
Dies funktioniert nicht, wenn RAND_MAX == INT_MAX (wie auf den meisten Systemen) . Siehe meinen zweiten Kommentar zu @ user1413793 oben.
BlueRaja - Danny Pflughoeft
19

@ user1413793 ist bezüglich des Problems korrekt. Ich werde das nicht weiter diskutieren, außer um einen Punkt zu machen: Ja, für kleine Werte nund große Werte von RAND_MAXkann die Modulo-Vorspannung sehr klein sein. Die Verwendung eines Bias-induzierenden Musters bedeutet jedoch, dass Sie die Bias jedes Mal berücksichtigen müssen, wenn Sie eine Zufallszahl berechnen und unterschiedliche Muster für verschiedene Fälle auswählen. Und wenn Sie die falsche Wahl treffen, sind die darin enthaltenen Fehler subtil und für Unit-Tests fast unmöglich. Verglichen mit der Verwendung des richtigen Werkzeugs (z. B. arc4random_uniform) ist dies zusätzliche Arbeit, nicht weniger Arbeit. Mehr Arbeit zu leisten und eine schlechtere Lösung zu finden, ist eine schreckliche Technik, besonders wenn es auf den meisten Plattformen einfach ist, es jedes Mal richtig zu machen.

Leider sind die Implementierungen der Lösung alle falsch oder weniger effizient als sie sein sollten. (Jede Lösung enthält verschiedene Kommentare, in denen die Probleme erläutert werden, aber keine der Lösungen wurde behoben, um sie zu beheben.) Dies kann den gelegentlichen Antwortsuchenden verwirren. Daher biete ich hier eine bekanntermaßen gute Implementierung an.

Auch hier ist die beste Lösung die Verwendung arc4random_uniformauf Plattformen, die sie bereitstellen, oder eine ähnliche Fernkampflösung für Ihre Plattform (z. B. Random.nextIntauf Java). Es wird das Richtige ohne Codekosten für Sie tun. Dies ist fast immer der richtige Anruf.

Wenn dies nicht der Fall ist, arc4random_uniformkönnen Sie die Leistung von Open Source nutzen, um genau zu sehen, wie es auf einem RNG mit größerer Reichweite implementiert wird ( ar4randomin diesem Fall könnte ein ähnlicher Ansatz jedoch auch auf anderen RNGs funktionieren).

Hier ist die OpenBSD-Implementierung :

/*
 * 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.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Es ist erwähnenswert, dass der neueste Commit-Kommentar zu diesem Code für diejenigen gedacht ist, die ähnliche Dinge implementieren müssen:

Ändern Sie arc4random_uniform (), um zu berechnen 2**32 % upper_boundals -upper_bound % upper_bound. Vereinfacht den Code und macht ihn auf ILP32- und LP64-Architekturen gleich und auf LP64-Architekturen etwas schneller, indem ein 32-Bit-Rest anstelle eines 64-Bit-Rest verwendet wird.

Von Jorden Verwer auf tech @ ok deraadt hervorgehoben; Keine Einwände von DJM oder Otto

Die Java-Implementierung ist auch leicht zu finden (siehe vorherigen Link):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }
Rob Napier
quelle
Beachten Sie, dass arcfour_random() die Ausgabe definitiv eine gewisse Verzerrung aufweist , wenn tatsächlich der echte RC4-Algorithmus in seiner Implementierung verwendet wird. Hoffentlich haben Ihre Bibliotheksautoren auf die Verwendung eines besseren CSPRNG hinter derselben Schnittstelle umgestellt. Ich erinnere mich, dass eines der BSDs jetzt tatsächlich den ChaCha20-Algorithmus zur Implementierung verwendet arcfour_random(). Weitere Informationen
rmalayter
2
@rmalayter Unter iOS und OS X liest arc4random aus / dev / random, was die Entropie mit der höchsten Qualität im System darstellt. (Der "arc4" im Namen ist historisch und aus Kompatibilitätsgründen erhalten.)
Rob Napier
@Rob_Napier gut zu wissen, hat aber /dev/randomin der Vergangenheit auch RC4 auf einigen Plattformen verwendet (Linux verwendet SHA-1 im Zählermodus). Leider weisen die über die Suche gefundenen Manpages darauf hin, dass RC4 auf verschiedenen angebotenen Plattformen noch verwendet wird arc4random(obwohl der tatsächliche Code möglicherweise unterschiedlich ist).
Rmalayter
1
Ich bin verwirrt. Ist nicht -upper_bound % upper_bound == 0??
Jon McClung
1
@JonMcClung ist -upper_bound % upper_boundin der Tat 0, wenn intes breiter als 32 Bit ist. Es sollte sein (u_int32_t)-upper_bound % upper_bound)(vorausgesetzt, es u_int32_tist ein BSD-Ismus für uint32_t).
Ian Abbott
14

Definition

Modulo Bias ist die inhärente Vorspannung bei der Verwendung von Modulo-Arithmetik, um einen Ausgangssatz auf eine Teilmenge des Eingangssatzes zu reduzieren. Im Allgemeinen liegt eine Vorspannung vor, wenn die Zuordnung zwischen dem Eingabe- und dem Ausgabesatz nicht gleichmäßig verteilt ist, wie im Fall der Verwendung der Modulo-Arithmetik, wenn die Größe des Ausgabesatzes kein Teiler der Größe des Eingabesatzes ist.

Diese Verzerrung ist besonders schwer zu vermeiden, wenn Zahlen als Bitfolgen dargestellt werden: 0s und 1s. Es ist ebenfalls äußerst schwierig, wirklich zufällige Zufallsquellen zu finden, die jedoch den Rahmen dieser Diskussion sprengen. Nehmen Sie für den Rest dieser Antwort an, dass es eine unbegrenzte Quelle für wirklich zufällige Bits gibt.

Problembeispiel

Betrachten wir die Simulation eines Würfelwurfs (0 bis 5) mit diesen zufälligen Bits. Es gibt 6 Möglichkeiten, also brauchen wir genug Bits, um die Zahl 6 darzustellen, die 3 Bits ist. Leider ergeben 3 zufällige Bits 8 mögliche Ergebnisse:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Wir können die Größe des Ergebnissatzes auf genau 6 reduzieren, indem wir den Wert modulo 6 nehmen. Dies stellt jedoch das Modulo-Bias- Problem dar: 110ergibt eine 0 und 111ergibt eine 1. Dieser Würfel wird geladen.

Potentielle Lösungen

Ansatz 0:

Anstatt sich auf zufällige Bits zu verlassen, könnte man theoretisch eine kleine Armee einstellen, die den ganzen Tag würfelt und die Ergebnisse in einer Datenbank aufzeichnet und dann jedes Ergebnis nur einmal verwendet. Dies ist ungefähr so ​​praktisch, wie es sich anhört, und würde höchstwahrscheinlich sowieso keine wirklich zufälligen Ergebnisse liefern (Wortspiel beabsichtigt).

Ansatz 1:

Anstatt das Modul zu verwenden, eine naive , aber mathematisch korrekte Lösung ist zu verwerfen Ergebnisse , dass Ausbeute 110und 111und einfach versuchen Sie es erneut mit 3 neuen Bits. Leider bedeutet dies, dass bei jedem Wurf eine 25% ige Chance besteht, dass ein erneuter Wurf erforderlich ist, einschließlich jedes der erneuten Würfe selbst. Dies ist eindeutig unpraktisch für alle außer den trivialsten Verwendungen.

Ansatz 2:

Verwenden Sie mehr Bits: Verwenden Sie anstelle von 3 Bits 4. Dies ergibt 16 mögliche Ergebnisse. Ein erneutes Rollen, wenn das Ergebnis größer als 5 ist, macht die Sache natürlich noch schlimmer (10/16 = 62,5%), so dass allein nichts hilft.

Beachten Sie, dass 2 * 6 = 12 <16 ist, sodass wir sicher jedes Ergebnis unter 12 nehmen und dieses Modulo 6 reduzieren können, um die Ergebnisse gleichmäßig zu verteilen. Die anderen 4 Ergebnisse müssen verworfen und dann wie im vorherigen Ansatz erneut gewürfelt werden.

Hört sich zunächst gut an, aber lassen Sie uns die Mathematik überprüfen:

4 discarded results / 16 possibilities = 25%

In diesem Fall hat 1 zusätzliches Bit überhaupt nicht geholfen !

Dieses Ergebnis ist unglücklich, aber versuchen wir es noch einmal mit 5 Bits:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Eine deutliche Verbesserung, aber in vielen praktischen Fällen nicht gut genug. Die gute Nachricht ist, dass das Hinzufügen weiterer Bits niemals die Wahrscheinlichkeit erhöht, dass ein Abwurf und ein erneuter Wurf erforderlich sind . Dies gilt nicht nur für Würfel, sondern in allen Fällen.

Wie gezeigt , ändert das Hinzufügen eines zusätzlichen Bits möglicherweise nichts. Wenn wir unseren Roll auf 6 Bit erhöhen, bleibt die Wahrscheinlichkeit 6,25%.

Dies wirft 2 zusätzliche Fragen auf:

  1. Wenn wir genügend Bits hinzufügen, gibt es eine Garantie dafür, dass die Wahrscheinlichkeit eines Verwerfens abnimmt?
  2. Wie viele Bits reichen im allgemeinen Fall aus?

Allgemeine Lösung

Zum Glück lautet die Antwort auf die erste Frage ja. Das Problem mit 6 ist, dass 2 ^ x mod 6 zwischen 2 und 4 wechselt, die zufällig ein Vielfaches von 2 voneinander sind, so dass für ein gerades x> 1

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Somit ist 6 eher eine Ausnahme als die Regel. Es ist möglich, größere Module zu finden, die auf die gleiche Weise aufeinanderfolgende Potenzen von 2 ergeben, aber letztendlich muss dies umlaufen, und die Wahrscheinlichkeit eines Verwerfens wird verringert.

Ohne weiteren Beweis bietet die Verwendung der doppelten Anzahl der erforderlichen Bits im Allgemeinen eine geringere, normalerweise unbedeutende Wahrscheinlichkeit eines Verwerfens.

Konzeptioneller Beweiß

Hier ist ein Beispielprogramm, das OpenSSLs libcrypo verwendet, um zufällige Bytes bereitzustellen. Stellen Sie beim Kompilieren sicher, dass Sie eine Verknüpfung zu der Bibliothek herstellen, mit -lcryptoder fast jeder verfügbar sein sollte.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

Ich empfehle, mit den Werten MODULUSund zu spielen ROLLS, um zu sehen, wie viele Wiederholungen unter den meisten Bedingungen tatsächlich stattfinden. Eine skeptische Person möchte möglicherweise auch die berechneten Werte in einer Datei speichern und überprüfen, ob die Verteilung normal erscheint.

Jim Wood
quelle
Ich hoffe wirklich, dass niemand Ihre einheitliche zufällige Implementierung blind kopiert hat. Die randomPool = RAND_bytes(...)Zeile führt randomPool == 1aufgrund der Behauptung immer zu. Dies führt immer zu einem Abwurf und einem erneuten Wurf. Ich denke, Sie wollten in einer separaten Zeile deklarieren. Infolgedessen kehrte das RNG bei 1jeder Iteration zurück.
Qix - MONICA wurde am
Um klar zu sein, randomPoolwird immer 1nach der OpenSSL- DokumentationRAND_bytes() ausgewertet, da es dank der RAND_status()Behauptung immer erfolgreich sein wird .
Qix - MONICA wurde am
9

Es gibt zwei übliche Beschwerden bei der Verwendung von Modulo.

  • Einer gilt für alle Generatoren. In einem Grenzfall ist es leichter zu erkennen. Wenn Ihr Generator einen RAND_MAX hat, der 2 ist (was nicht dem C-Standard entspricht) und Sie nur 0 oder 1 als Wert möchten, generiert modulo 0 doppelt so oft (wenn der Generator 0 und 2 generiert) wie es ist 1 generieren (wenn der Generator 1 generiert). Beachten Sie, dass dies der Fall ist, sobald Sie keine Werte löschen, unabhängig von der Zuordnung, die Sie von den Generatorwerten zu den gewünschten verwenden, eine doppelt so häufig wie die andere.

  • Bei einigen Generatoren sind die weniger signifikanten Bits weniger zufällig als bei den anderen, zumindest für einige ihrer Parameter. Leider weisen diese Parameter andere interessante Eigenschaften auf (z. B. kann RAND_MAX eine weniger als eine Potenz von 2 haben). Das Problem ist bekannt und für eine lange Zeit vermeiden Bibliotheksimplementierungen wahrscheinlich das Problem (zum Beispiel verwendet die Beispiel-Implementierung von rand () im C-Standard diese Art von Generator, lässt aber die 16 weniger signifikanten Bits fallen), aber einige beschweren sich gerne darüber das und Sie können Pech haben

Mit so etwas wie

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

Das Generieren einer Zufallszahl zwischen 0 und n vermeidet beide Probleme (und vermeidet einen Überlauf mit RAND_MAX == INT_MAX).

Übrigens führte C ++ 11 Standardmethoden für die Reduktion und andere Generatoren als rand () ein.

Ein Programmierer
quelle
n == RAND_MAX? 1: (RAND_MAX-1) / (n + 1): Ich verstehe, dass die Idee hier darin besteht, zuerst RAND_MAX in die gleiche Seitengröße N zu teilen und dann die Abweichung innerhalb von N zurückzugeben, aber ich kann den Code nicht genau darauf abbilden.
Zinking
1
Die naive Version sollte (RAND_MAX + 1) / (n + 1) sein, da RAND_MAX + 1-Werte in n + 1 Buckets unterteilt werden müssen. Um einen Überlauf bei der Berechnung von RAND_MAX + 1 zu vermeiden, kann dieser in 1+ (RAND_MAX-n) / (n + 1) transformiert werden. Um einen Überlauf bei der Berechnung von n + 1 zu vermeiden, wird zunächst der Fall n == RAND_MAX geprüft.
AProgrammer
+ plus, Divide zu machen scheint im Vergleich zu regenerierten Zahlen sogar mehr zu kosten.
Zinking
4
Das Modulo zu nehmen und zu teilen haben die gleichen Kosten. Einige ISA bieten sogar nur eine Anweisung an, die immer beide bereitstellt. Die Kosten für die Regenerierung von Zahlen hängen von n und RAND_MAX ab. Wenn n in Bezug auf RAND_MAX klein ist, kann es viel kosten. Und natürlich können Sie entscheiden, dass die Verzerrungen für Ihre Anwendung nicht wichtig sind. Ich gebe nur einen Weg, um sie zu vermeiden.
AProgrammer
9

Marks Lösung (die akzeptierte Lösung) ist nahezu perfekt.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

bearbeitet am 25. März 16 um 23:16 Uhr

Mark Amery 39k21170211

Es gibt jedoch eine Einschränkung, die 1 gültigen Satz von Ergebnissen in jedem Szenario verwirft, in dem RAND_MAX( RM) 1 weniger als ein Vielfaches von N(wobei N= die Anzahl möglicher gültiger Ergebnisse) ist.

dh wenn die 'Anzahl der verworfenen Werte' ( D) gleich ist N, dann sind sie tatsächlich eine gültige Menge ( V)keine ungültige Menge ( I).

Was dies verursacht, ist, dass Mark irgendwann den Unterschied zwischen Nund aus den Augen verliert Rand_Max.

Nist eine Menge, deren gültige Mitglieder nur aus positiven Ganzzahlen bestehen, da sie eine Anzahl von Antworten enthält, die gültig wären. (zB: Set N= {1, 2, 3, ... n })

Rand_max Es handelt sich jedoch um eine Menge, die (wie für unsere Zwecke definiert) eine beliebige Anzahl nicht negativer Ganzzahlen enthält.

In seiner allgemeinsten Form wird hier Rand Maxdie Menge aller gültigen Ergebnisse definiert, die theoretisch negative Zahlen oder nicht numerische Werte enthalten können.

Daher Rand_Maxist besser definiert als die Menge der "möglichen Antworten".

Jedoch Narbeitet gegen die Zählung der Werte innerhalb des Satzes von gültigen Antworten, so auch wie in unserem speziellen Fall definiert ist , Rand_Maxwird ein Wert um eins kleiner als die Gesamtzahl sei es enthält.

Bei Verwendung von Marks Lösung werden Werte verworfen, wenn: X => RM - RM% N.

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Wie Sie im obigen Beispiel sehen können, würden wir den Wert von X (die Zufallszahl, die wir aus der Anfangsfunktion erhalten) 252, 253, 254 oder 255 verwerfen, obwohl diese vier Werte einen gültigen Satz zurückgegebener Werte enthalten .

IE: Wenn die Anzahl der verworfenen Werte (I) = N (die Anzahl der gültigen Ergebnisse) ist, wird ein gültiger Satz von Rückgabewerten von der ursprünglichen Funktion verworfen.

Wenn wir den Unterschied zwischen den Werten N und RM als D beschreiben, dh:

D = (RM - N)

Wenn dann der Wert von D kleiner wird, steigt der Prozentsatz der nicht benötigten Nachwürfe aufgrund dieser Methode bei jedem natürlichen Multiplikativ. (Wenn RAND_MAX NICHT gleich einer Primzahl ist, ist dies von berechtigter Bedeutung.)

Z.B:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Da der Prozentsatz der benötigten Rerolls zunimmt, je näher N an RM kommt, kann dies bei vielen verschiedenen Werten von Bedeutung sein, abhängig von den Einschränkungen des Systems, auf dem der Code ausgeführt wird, und den gesuchten Werten.

Um dies zu negieren, können wir eine einfache Änderung vornehmen, wie hier gezeigt:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

Dies bietet eine allgemeinere Version der Formel, die die zusätzlichen Besonderheiten der Verwendung des Moduls zur Definition Ihrer Maximalwerte berücksichtigt.

Beispiele für die Verwendung eines kleinen Werts für RAND_MAX, der ein Multiplikativ von N ist.

Mark'original Version:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Verallgemeinerte Version 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

In dem Fall, in dem N die Anzahl der Werte in RAND_MAX sein soll; In diesem Fall können Sie N = RAND_MAX +1 setzen, es sei denn, RAND_MAX = INT_MAX.

In Bezug auf die Schleife können Sie einfach N = 1 verwenden, und jeder Wert von X wird jedoch akzeptiert, und Sie geben eine IF-Anweisung für Ihren endgültigen Multiplikator ein. Aber vielleicht haben Sie Code, der einen gültigen Grund hat, eine 1 zurückzugeben, wenn die Funktion mit n = 1 aufgerufen wird ...

Daher ist es möglicherweise besser, 0 zu verwenden, was normalerweise einen Div 0-Fehler liefert, wenn Sie n = RAND_MAX + 1 haben möchten

Verallgemeinerte Version 2:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

Beide Lösungen lösen das Problem mit unnötig verworfenen gültigen Ergebnissen, die auftreten, wenn RM + 1 ein Produkt von n ist.

Die zweite Version behandelt auch das Edge-Case-Szenario, wenn Sie n benötigen, um dem insgesamt möglichen Wertesatz in RAND_MAX zu entsprechen.

Der modifizierte Ansatz ist in beiden Fällen derselbe und ermöglicht eine allgemeinere Lösung für die Notwendigkeit, gültige Zufallszahlen bereitzustellen und verworfene Werte zu minimieren.

Wiederholen:

Die grundlegende allgemeine Lösung, die das Beispiel der Marke erweitert:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

 x %= n;

Die erweiterte allgemeine Lösung, die ein zusätzliches Szenario von RAND_MAX + 1 = n ermöglicht:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

    x %= n;
} else {
    x = rand();
}

In einigen Sprachen (insbesondere interpretierten Sprachen) kann die Berechnung der Vergleichsoperation außerhalb der while-Bedingung zu schnelleren Ergebnissen führen, da dies eine einmalige Berechnung ist, unabhängig davon, wie viele Versuche erforderlich sind. YMMV!

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x; // Resulting random number
int y; // One-time calculation of the compare value for x

if n != 0 {
    y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 
    do {
        x = rand();
    } while (x > y);

    x %= n;
} else {
    x = rand();
}
Ben Personick
quelle
Ist es nicht sicher zu sagen, dass das Problem mit Marks Lösung darin besteht, dass er RAND_MAX und n als dieselbe "Maßeinheit" behandelt, obwohl sie tatsächlich zwei verschiedene Dinge bedeuten? Während n die resultierende "Anzahl von Möglichkeiten" darstellt, stellt RAND_MAX nur den Maximalwert der ursprünglichen Möglichkeit dar, wobei RAND_MAX + 1 die ursprüngliche Anzahl von Möglichkeiten wäre. Ich bin überrascht, dass er nicht zu Ihrem Schluss gekommen ist, da er anscheinend anerkannt hat, dass n und RAND_MAX nicht dasselbe mit der Gleichung waren:RAND_MAX%n = n - 1
Danilo Souza Morães
@ DaniloSouzaMorães Danke Danilo, Sie haben die Angelegenheit sehr prägnant formuliert. Ich wollte demonstrieren, was er zusammen mit dem Warum und Wie tat, aber ich glaube nicht, dass ich jemals sagen konnte, WAS er eloquent falsch gemacht hat, da ich so in die Details der Logik verwickelt bin, wie und warum es ein Problem gibt, das ich nicht so klar darlege, worum es geht. Stört es Sie, wenn ich meine Antwort dahingehend ändere, dass ich einen Teil dessen, was Sie hier geschrieben haben, als meine eigene Zusammenfassung für die Frage verwende, was und wo die akzeptierte Lösung tut, was oben angesprochen werden muss?
Ben Personick
Das wäre super. Los geht's
Danilo Souza Morães
1

Bei einem RAND_MAXWert von 3(in Wirklichkeit sollte er viel höher sein, aber die Verzerrung würde immer noch bestehen) ist es aus diesen Berechnungen sinnvoll, dass eine Verzerrung vorliegt:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

In diesem Fall % 2sollten Sie dies nicht tun, wenn Sie eine Zufallszahl zwischen 0und möchten 1. Sie könnten eine Zufallszahl zwischen bekommen 0und 2indem % 3aber, weil in diesem Fall:RAND_MAX ein Vielfaches 3.

Eine andere Methode

Es ist viel einfacher, aber um andere Antworten zu ergänzen, hier ist meine Lösung, um eine Zufallszahl zwischen 0und n - 1, also nverschiedene Möglichkeiten, ohne Verzerrung zu erhalten.

  • Die Anzahl der Bits (nicht Bytes), die zum Codieren der Anzahl der Möglichkeiten benötigt werden, ist die Anzahl der Bits zufälliger Daten, die Sie benötigen
  • codiere die Zahl aus zufälligen Bits
  • Wenn diese Nummer lautet >= n, starten Sie neu (kein Modulo).

Wirklich zufällige Daten sind nicht einfach zu erhalten. Warum also mehr Bits als nötig verwenden?

Unten sehen Sie ein Beispiel in Smalltalk, bei dem ein Bit-Cache eines Pseudozufallszahlengenerators verwendet wird. Ich bin kein Sicherheitsexperte. Die Verwendung erfolgt auf eigenes Risiko.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r
Rivenfall
quelle
-1

Wie die akzeptierte Antwort zeigt, hat "Modulo Bias" seine Wurzeln im niedrigen Wert von RAND_MAX. Er verwendet einen extrem kleinen Wert von RAND_MAX(10), um zu zeigen, dass, wenn RAND_MAX 10 wäre, Sie versucht hätten, mit% eine Zahl zwischen 0 und 2 zu generieren, die folgenden Ergebnisse resultieren würden:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

Es gibt also 4 Ausgänge von 0 (4/10 Chance) und nur 3 Ausgänge von 1 und 2 (jeweils 3/10 Chancen).

Es ist also voreingenommen. Die niedrigeren Zahlen haben eine bessere Chance herauszukommen.

Aber das zeigt sich nur so offensichtlich, wenn RAND_MAXes klein ist . Oder genauer gesagt, wenn die Anzahl, nach der Sie modifizieren, im Vergleich zu groß istRAND_MAX .

Eine viel bessere Lösung als eine Schleife (die wahnsinnig ineffizient ist und nicht einmal vorgeschlagen werden sollte) ist die Verwendung eines PRNG mit einem viel größeren Ausgabebereich. Der Mersenne Twister- Algorithmus hat eine maximale Leistung von 4.294.967.295. Als solches wird das Tun MersenneTwister::genrand_int32() % 10in jeder Hinsicht gleichmäßig verteilt und der Modulo-Bias-Effekt wird so gut wie verschwinden.

Bobobobo
quelle
3
Ihre ist effizienter und es ist wahrscheinlich richtig, dass wenn RAND_MAX signifikant größer ist als die Zahl, um die Sie modifizieren, Ihre jedoch immer noch voreingenommen ist. Zugegeben, dies sind sowieso alle Pseudozufallszahlengeneratoren, und das an und für sich ist ein anderes Thema, aber wenn Sie einen vollständig zufälligen Zahlengenerator annehmen, werden die niedrigeren Werte immer noch verzerrt.
user1413793
Da der höchste Wert ungerade ist, werden MT::genrand_int32()%20 (50 + 2,3e-8)% der Zeit und 1 (50 - 2,3e-8)% der Zeit ausgewählt. Sofern Sie nicht die RGN eines Casinos erstellen (für die Sie wahrscheinlich eine RGN mit viel größerer Reichweite verwenden würden), wird kein Benutzer in den meisten Fällen zusätzliche 2,3e-8% bemerken. Sie sprechen von Zahlen, die zu klein sind, um hier eine Rolle zu spielen.
Bobobobo
7
Looping ist die beste Lösung. Es ist nicht "wahnsinnig ineffizient"; im schlimmsten Durchschnitt weniger als das Doppelte der Iterationen erforderlich. Die Verwendung eines hohen RAND_MAXWerts verringert die Modulo-Vorspannung, beseitigt sie jedoch nicht. Looping wird.
Jared Nielsen
5
Wenn RAND_MAXes ausreichend größer ist als die Zahl, mit der Sie modifizieren, ist die Häufigkeit, mit der Sie die Zufallszahl neu generieren müssen, verschwindend gering und beeinträchtigt die Effizienz nicht. Ich sage, behalte die Schleife bei, solange du gegen das größte Vielfache von ntestest und nicht nur so, nwie es die akzeptierte Antwort vorschlägt.
Mark Ransom
-3

Ich habe gerade einen Code für Von Neumanns Unbiased Coin Flip-Methode geschrieben, der theoretisch jegliche Verzerrung bei der Zufallszahlengenerierung beseitigen sollte. Weitere Infos finden Sie unter ( http://en.wikipedia.org/wiki/Fair_coin )

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}
Yavuz Koroglu
quelle
Dies spricht nicht die Modulo-Vorspannung an. Dieser Prozess könnte verwendet werden, um eine Vorspannung in einem Bitstrom zu beseitigen. Um jedoch von einem Bitstrom zu einer gleichmäßigen Verteilung von 0 nach n zu gelangen, wobei n nicht eins weniger als eine Zweierpotenz ist, muss die Modulo-Vorspannung adressiert werden. Somit kann diese Lösung keine Verzerrung im Zufallszahlengenerierungsprozess
Rick
2
@ Rick hmm. Die logische Erweiterung von Von Neumanns Methode zur Beseitigung der Modulo-Verzerrung beim Erzeugen einer Zufallszahl zwischen beispielsweise 1 und 100 wäre: A) rand() % 100100-maliger Aufruf . B) Wenn alle Ergebnisse unterschiedlich sind, nehmen Sie das erste. C) Andernfalls GOTO A. Dies wird funktionieren, aber mit einer erwarteten Anzahl von Iterationen von ungefähr 10 ^ 42 müssen Sie ziemlich geduldig sein. Und unsterblich.
Mark Amery
@ MarkAmery In der Tat sollte das funktionieren. Schauen Sie sich diesen Algorithmus an, obwohl er nicht korrekt implementiert ist. Das erste sollte sein:else if(prev==2) prev= x1; else { if(prev!=x1) return prev; prev=2;}
Rick