Warum ist rand ()% 6 voreingenommen?

Beim Lesen der Verwendung von std :: rand habe ich diesen Code auf cppreference.com gefunden

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

Was ist falsch an dem Ausdruck auf der rechten Seite? Versuchte es und es funktioniert perfekt.

Es gibt zwei Probleme mit rand() % 6(das 1+betrifft keines der beiden Probleme).

Erstens ist, wie mehrere Antworten gezeigt haben rand(), das Ergebnis des Restoperators auch nicht einheitlich , wenn die niedrigen Bits von nicht angemessen einheitlich sind.

Zweitens, wenn die Anzahl der von erzeugten unterschiedlichen Werte rand()kein Vielfaches von 6 ist, erzeugt der Rest mehr niedrige Werte als hohe Werte. Dies gilt auch dann, wenn rand()perfekt verteilte Werte zurückgegeben werden.

Stellen Sie sich als extremes Beispiel vor, dass rand()gleichmäßig verteilte Werte im Bereich erzeugt werden [0..6]. Wenn Sie sich die Reste für diese Werte ansehen und rand()einen Wert im Bereich zurückgeben [0..5], führt der Rest zu gleichmäßig verteilten Ergebnissen im Bereich [0..5]. Wenn rand()6 zurückgegeben wird, wird rand() % 60 zurückgegeben, als hätte 0 rand()zurückgegeben. Sie erhalten also eine Verteilung mit doppelt so vielen Nullen wie jeder andere Wert.

Das zweite ist das eigentliche Problem mit rand() % 6.

Um dieses Problem zu vermeiden, müssen Werte verworfen werden, die zu ungleichmäßigen Duplikaten führen würden. Sie berechnen das größte Vielfache von 6, das kleiner oder gleich ist RAND_MAX, und wenn Sie rand()einen Wert zurückgeben, der größer oder gleich diesem Vielfachen ist, lehnen Sie es ab und rufen `rand () erneut auf, so oft dies erforderlich ist.

So:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

Dies ist eine andere Implementierung des fraglichen Codes, um klarer zu zeigen, was los ist.

Hier gibt es verborgene Tiefen:

1. Die Verwendung des kleinen uin RAND_MAX + 1u. RAND_MAXwird als intTyp definiert und ist oft der größtmögliche int. Das Verhalten von RAND_MAX + 1wäre in solchen Fällen undefiniert, in denen Sie einen signedTyp überlaufen würden . Das Schreiben 1uerzwingt die Typkonvertierung von RAND_MAXin unsigned, wodurch der Überlauf vermieden wird.

2. Die Verwendung von % 6 can (aber bei jeder Implementierung von can , die std::randich nicht gesehen habe ) führt zu zusätzlichen statistischen Verzerrungen, die über die vorgestellte Alternative hinausgehen. Solche Fälle, in denen dies % 6gefährlich ist, sind Fälle, in denen der Zahlengenerator Korrelationsebenen in den Bits niedriger Ordnung aufweist, wie beispielsweise eine ziemlich berühmte IBM-Implementierung (in C) aus randden 1970er Jahren, in der die hohen und niedrigen Bits als "endgültig" umgedreht wurden blühen". Eine weitere Überlegung ist, dass 6 sehr klein ist, vgl. RAND_MAXEs wird also einen minimalen Effekt geben, wenn RAND_MAXnicht ein Vielfaches von 6 ist, was wahrscheinlich nicht der Fall ist.

Zusammenfassend würde ich heutzutage aufgrund seiner Traktierbarkeit verwenden % 6. Es ist unwahrscheinlich, dass statistische Anomalien auftreten, die über die vom Generator selbst eingeführten hinausgehen. Wenn Sie immer noch Zweifel haben, testen Sie Ihren Generator , um festzustellen, ob er die entsprechenden statistischen Eigenschaften für Ihren Anwendungsfall aufweist.

Dieser Beispielcode zeigt, dass std::randes sich um einen alten Frachtkult-Balderdash handelt, bei dem Ihre Augenbrauen jedes Mal hochgezogen werden sollten, wenn Sie ihn sehen.

Hier gibt es mehrere Probleme:

Die Vertragsleute gehen normalerweise davon aus - selbst die armen, unglücklichen Seelen, die es nicht besser wissen und nicht genau so denken -, dass randStichproben aus der gleichmäßigen Verteilung auf die ganzen Zahlen in 0, 1, 2,… RAND_MAX,, und jeder Aufruf ergibt eine unabhängige Stichprobe.

Das erste Problem besteht darin, dass der angenommene Vertrag, unabhängige einheitliche Zufallsstichproben bei jedem Aufruf, nicht den Angaben in der Dokumentation entspricht - und in der Praxis haben Implementierungen in der Vergangenheit nicht einmal das geringste Simulakrum der Unabhängigkeit geliefert. Zum Beispiel randsagt C99 §7.20.2.1 'Die Funktion' ohne Ausarbeitung:

Die randFunktion berechnet eine Folge von Pseudozufallszahlen im Bereich von 0 bis RAND_MAX.

Dies ist ein bedeutungsloser Satz, da Pseudozufälligkeit eine Eigenschaft einer Funktion (oder Funktionsfamilie ) ist, nicht einer ganzen Zahl, aber das hindert nicht einmal ISO-Bürokraten daran, die Sprache zu missbrauchen. Schließlich wissen die einzigen Leser, die sich darüber aufregen würden, besser, als die Dokumentation zu lesen, randweil sie befürchten, dass ihre Gehirnzellen verfallen.

Eine typische historische Implementierung in C funktioniert folgendermaßen:

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

Dies hat die unglückliche Eigenschaft, dass eine einzelne Stichprobe , obwohl sie unter einem einheitlichen zufälligen Startwert (der vom spezifischen Wert von abhängt) gleichmäßig verteilt sein kann,RAND_MAX bei aufeinanderfolgenden Aufrufen nachher zwischen geraden und ungeraden Ganzzahlen wechselt

int a = rand();
int b = rand();

Der Ausdruck (a & 1) ^ (b & 1)ergibt 1 mit einer Wahrscheinlichkeit von 100%, was bei unabhängigen Zufallsstichproben für jede Verteilung, die auf geraden und ungeraden ganzen Zahlen unterstützt wird, nicht der Fall ist . So entstand ein Frachtkult, dass man die niederwertigen Teile wegwerfen sollte, um das schwer fassbare Tier der "besseren Zufälligkeit" zu jagen. (Spoiler-Alarm: Dies ist kein Fachbegriff. Dies ist ein Zeichen dafür, dass die Prosa, über die Sie lesen, entweder nicht weiß, wovon sie sprechen, oder dass Sie ahnungslos sind und sich herablassen müssen.)

Das zweite Problem ist, dass selbst wenn jeder Aufruf unabhängig von einer gleichmäßigen Zufallsverteilung auf 0, 1, 2, ... RAND_MAXabgetastet rand() % 6würde , das Ergebnis von nicht wie ein Würfel in 0, 1, 2, 3, 4, 5 gleichmäßig verteilt wäre roll, es RAND_MAXsei denn, es ist kongruent zu -1 modulo 6. Einfaches Gegenbeispiel: Wenn RAND_MAX= 6, dann rand()haben alle Ergebnisse die gleiche Wahrscheinlichkeit 1/7, aber ab rand() % 6hat das Ergebnis 0 die Wahrscheinlichkeit 2/7, während alle anderen Ergebnisse die Wahrscheinlichkeit 1/7 haben .

Der richtige Weg, dies zu tun, ist die Ablehnungsstichprobe: Ziehen Sie wiederholt eine unabhängige einheitliche Zufallsstichprobe saus 0, 1, 2,… RAND_MAXund lehnen Sie (zum Beispiel) die Ergebnisse 0, 1, 2,… ab - ((RAND_MAX + 1) % 6) - 1wenn Sie eine von erhalten diese fangen von vorne an; ansonsten ergeben s % 6.

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

Auf diese Weise ist die Menge der Ergebnisse rand(), die wir akzeptieren, gleichmäßig durch 6 teilbar, und jedes mögliche Ergebnis von s % 6wird durch die gleiche Anzahl akzeptierter Ergebnisse von erhalten rand(). Wenn rand()es also gleichmäßig verteilt ist, ist dies auch der Fall s. Die Anzahl der Versuche ist nicht begrenzt , aber die erwartete Anzahl beträgt weniger als 2, und die Erfolgswahrscheinlichkeit steigt exponentiell mit der Anzahl der Versuche.

Die Wahl, welche Ergebnisse rand()Sie ablehnen, ist unerheblich, vorausgesetzt, Sie ordnen jeder Ganzzahl unter 6 eine gleiche Anzahl zu. Der Code auf cppreference.com trifft aufgrund des ersten oben genannten Problems eine andere Wahl: Es wird nichts über das garantiert Verteilung oder Unabhängigkeit der Ausgaben von rand()und in der Praxis zeigten die niederwertigen Bits Muster, die nicht zufällig genug aussehen (egal, dass die nächste Ausgabe eine deterministische Funktion der vorherigen ist).

Übung für den Leser: Beweisen Sie, dass der Code auf cppreference.com eine gleichmäßige Verteilung auf Würfelrollen ergibt, wenn er rand()eine gleichmäßige Verteilung auf 0, 1, 2,… , RAND_MAX.

Übung für den Leser: Warum möchten Sie vielleicht die eine oder andere Teilmenge ablehnen? Welche Berechnung ist in beiden Fällen für jeden Versuch erforderlich?

Ein drittes Problem ist, dass der Samenraum so klein ist, dass selbst wenn der Samen gleichmäßig verteilt ist, ein Gegner, der mit Kenntnis Ihres Programms und einem Ergebnis, aber nicht dem Samen ausgestattet ist, den Samen und die nachfolgenden Ergebnisse leicht vorhersagen kann, was sie nicht so erscheinen lässt Immerhin zufällig. Denken Sie also nicht einmal daran, dies für die Kryptografie zu verwenden.

std::uniform_int_distributionMit einem geeigneten Zufallsgerät und Ihrer bevorzugten Zufalls-Engine wie dem allseits beliebten Mersenne-Twister können Sie die ausgefallene überentwickelte Route und die Klasse von C ++ 11 gehen std::mt19937, um mit Ihrem vierjährigen Cousin Würfel zu spielen, aber selbst das wird nicht fit sein für kryptographischen Schlüssel Material-und die Mersenne Erzeugung Twister ein schrecklichen Raum Schwein mit einem Multi-Kilobyte Zustand verheerend auf Ihrem CPU-Cache mit einer obszönen Rüstzeit auch ist, so ist es schlecht , auch für ist, zB parallel Monte - Carlo - Simulationen mit reproduzierbare Bäume von Teilberechnungen; seine Popularität ergibt sich wahrscheinlich hauptsächlich aus seinem eingängigen Namen. Aber Sie können es für Spielzeugwürfel verwenden, die wie in diesem Beispiel rollen!

Ein anderer Ansatz besteht darin, einen einfachen kryptografischen Pseudozufallszahlengenerator mit einem kleinen Status zu verwenden, z. B. ein einfaches PRNG zum schnellen Löschen von Schlüsseln , oder nur eine Stream-Verschlüsselung wie AES-CTR oder ChaCha20, wenn Sie sicher sind ( z. B. in einer Monte-Carlo-Simulation für naturwissenschaftliche Forschung), dass die Vorhersage früherer Ergebnisse keine nachteiligen Folgen hat, wenn der Staat jemals kompromittiert wird.

Ich bin keineswegs ein erfahrener C ++ - Benutzer, war aber interessiert zu sehen, ob die anderen Antworten bezüglich std::rand()/((RAND_MAX + 1u)/6)weniger Voreingenommenheit als 1+std::rand()%6tatsächlich zutreffen. Also habe ich ein Testprogramm geschrieben, um die Ergebnisse für beide Methoden zu tabellieren (ich habe seit Jahren kein C ++ mehr geschrieben, bitte überprüfen Sie es). Einen Link zum Ausführen des Codes finden Sie hier . Es wird auch wie folgt reproduziert:

// Example program
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>

int main()
{
    std::srand(std::time(nullptr)); // use current time as seed for random generator

    // Roll the die 6000000 times using the supposedly unbiased method and keep track of the results

    int results[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

        results[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results[n] << ' ';
    }

    std::cout << "\n";


    // Roll the die 6000000 times using the supposedly biased method and keep track of the results

    int results_bias[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()%6;

        results_bias[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results_bias[n] << ' ';
    }
}

Ich habe dann die Ausgabe davon genommen und die chisq.testFunktion in R verwendet, um einen Chi-Quadrat-Test durchzuführen, um festzustellen, ob die Ergebnisse signifikant von den erwarteten abweichen. Diese Stapelaustauschfrage geht detaillierter auf die Verwendung des Chi-Quadrat-Tests zum Testen der Würfelgerechtigkeit ein: Wie kann ich testen, ob ein Würfel fair ist? . Hier sind die Ergebnisse für einige Läufe:

> ?chisq.test
> unbias <- c(100150, 99658, 100319, 99342, 100418, 100113)
> bias <- c(100049, 100040, 100091, 99966, 100188, 99666 )

> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 8.6168, df = 5, p-value = 0.1254

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 1.6034, df = 5, p-value = 0.9008

> unbias <- c(998630, 1001188, 998932, 1001048, 1000968, 999234 )
> bias <- c(1000071, 1000910, 999078, 1000080, 998786, 1001075   )
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.051, df = 5, p-value = 0.2169

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 4.319, df = 5, p-value = 0.5045

> unbias <- c(998630, 999010, 1000736, 999142, 1000631, 1001851)
> bias <- c(999803, 998651, 1000639, 1000735, 1000064,1000108)
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.9592, df = 5, p-value = 0.1585

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 2.8229, df = 5, p-value = 0.7273

In den drei Läufen, die ich durchgeführt habe, war der p-Wert für beide Methoden immer größer als die typischen Alpha-Werte, die zum Testen der Signifikanz verwendet wurden (0,05). Dies bedeutet, dass wir keinen von beiden als voreingenommen betrachten würden. Interessanterweise weist die vermeintlich unvoreingenommene Methode durchweg niedrigere p-Werte auf, was darauf hinweist, dass sie möglicherweise tatsächlich voreingenommener ist. Die Einschränkung ist, dass ich nur 3 Läufe gemacht habe.

UPDATE: Während ich meine Antwort schrieb, hat Konrad Rudolph eine Antwort gepostet, die den gleichen Ansatz verfolgt, aber ein ganz anderes Ergebnis erzielt. Ich habe nicht den Ruf, seine Antwort zu kommentieren, deshalb werde ich sie hier ansprechen. Erstens ist die Hauptsache, dass der Code, den er verwendet, bei jeder Ausführung denselben Startwert für den Zufallszahlengenerator verwendet. Wenn Sie den Samen ändern, erhalten Sie tatsächlich eine Vielzahl von Ergebnissen. Zweitens erhalten Sie eine Vielzahl von Ergebnissen, wenn Sie den Startwert nicht ändern, aber die Anzahl der Versuche ändern. Versuchen Sie, um eine Größenordnung zu erhöhen oder zu verringern, um zu sehen, was ich meine. Drittens gibt es einige ganzzahlige Kürzungen oder Rundungen, bei denen die erwarteten Werte nicht ganz genau sind. Es ist wahrscheinlich nicht genug, um einen Unterschied zu machen, aber es ist da.

Zusammenfassend lässt sich sagen, dass er zufällig den richtigen Samen und die richtige Anzahl von Versuchen erhalten hat, um ein falsches Ergebnis zu erzielen.

Man kann sich einen Zufallszahlengenerator als Arbeit an einem Strom von Binärziffern vorstellen. Der Generator wandelt den Stream in Zahlen um, indem er ihn in Stücke schneidet. Wenn die std:randFunktion mit einem RAND_MAXvon 32767 arbeitet, verwendet sie 15 Bits in jedem Slice.

Wenn man die Module einer Zahl zwischen 0 und einschließlich 32767 nimmt, findet man, dass 5462 '0' und '1', aber nur 5461 '2', '3', '4' und '5'. Daher ist das Ergebnis voreingenommen. Je größer der RAND_MAX-Wert ist, desto geringer ist die Vorspannung, die jedoch unvermeidlich ist.

Was nicht voreingenommen ist, ist eine Zahl im Bereich [0 .. (2 ^ n) -1]. Sie können eine (theoretisch) bessere Zahl im Bereich 0..5 erzeugen, indem Sie 3 Bits extrahieren, diese in eine Ganzzahl im Bereich 0..7 konvertieren und 6 und 7 ablehnen.

Man hofft, dass jedes Bit im Bitstrom die gleiche Chance hat, eine '0' oder eine '1' zu sein, unabhängig davon, wo es sich im Strom befindet oder welche Werte andere Bits haben. Dies ist in der Praxis außerordentlich schwierig. Die vielen verschiedenen Implementierungen von Software-PRNGs bieten unterschiedliche Kompromisse zwischen Geschwindigkeit und Qualität. Ein linearer Kongruenzgenerator std::randbietet beispielsweise die schnellste Geschwindigkeit bei niedrigster Qualität. Ein kryptografischer Generator bietet höchste Qualität bei niedrigster Geschwindigkeit.