Was mache ich falsch mit diesen Zufallszahlen?

Question

Mir wurde gesagt, dass rand() Mod n Verzerrungen erzeugt, also habe ich versucht, diesen Code zu machen, um es zu überprüfen. Es erzeugt s Zahlen von 1 bis l und sortiert dann nach Vorkommen.

#include <iostream> 
#include <random> 

using namespace std; 

struct vec_struct{ 
    int num; 
    int count; 
    double ratio; 
}; 

void num_sort(vec_struct v[], int n){ 
    for (int i = 0; i < n-1; i++){ 
     for (int k = 0; k < n-1-i; k++){ 
      if (v[k].num > v[k+1].num) swap(v[k], v[k+1]); 
     } 
    } 
} 

void count_sort(vec_struct v[], int n){ 
    for (int i = 0; i < n-1; i++){ 
     for (int k = 0; k < n-1-i; k++){ 
      if (v[k].count < v[k+1].count) swap(v[k], v[k+1]); 
     } 
    } 
} 

int main(){ 

    srand(time(0)); 

    random_device rnd; 

    int s, l, b, c = 1; 

    cout << "How many numbers to generate? "; 
    cin >> s; 

    cout << "Generate " << s << " numbers ranging from 1 to? "; 
    cin >> l; 

    cout << "Use rand or mt19937? [1/2] "; 
    cin >> b; 

    vec_struct * vec = new vec_struct[s]; 

    mt19937 engine(rnd()); 
    uniform_int_distribution <int> dist(1, l); 

    if (b == 1){ 
     for (int i = 0; i < s; i++){ 
      vec[i].num = (rand() % l) + 1; 
     } 
    } else if (b == 2){ 
     for (int i = 0; i < s; i++){ 
      vec[i].num = dist(engine); 
     } 
    } 
    num_sort(vec, s); 

    for (int i = 0, j = 0; i < s; i++){ 
     if (vec[i].num == vec[i+1].num){ 
      c++; 
     } else { 
      vec[j].num = vec[i].num; 
      vec[j].count = c; 
      vec[j].ratio = ((double)c/s)*100; 
      j++; 
      c = 1; 
     } 
    } 
    count_sort(vec, l); 

    if (l >= 20){ 

     cout << endl << "Showing the 10 most common numbers" << endl; 
     for (int i = 0; i < 10; i++){ 
      cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl; 
     } 

     cout << endl << "Showing the 10 least common numbers" << endl; 
     for (int i = l-10; i < l; i++){ 
      cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl; 
     } 
    } else { 

     for (int i = 0; i < l; i++){ 
      cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl; 
     } 
    } 
} 

Nach dem Ausführen dieses Codes kann ich die erwartete Vorspannung von rand() Ort:

$ ./rnd_test 
How many numbers to generate? 10000 
Generate 10000 numbers ranging from 1 to? 50 
Use rand or mt19937? [1/2] 1 

Showing the 10 most common numbers 
17 230 2.3% 
32 227 2.27% 
26 225 2.25% 
25 222 2.22% 
3 221 2.21% 
10 220 2.2% 
35 218 2.18% 
5 217 2.17% 
13 215 2.15% 
12 213 2.13% 

Showing the 10 least common numbers 
40 187 1.87% 
7 186 1.86% 
39 185 1.85% 
42 184 1.84% 
43 184 1.84% 
34 182 1.82% 
21 175 1.75% 
22 175 1.75% 
18 173 1.73% 
44 164 1.64% 

Hoover ich erhalte so ziemlich das gleiche Ergebnis mit mt19937 und uniform_int_distribution! Was ist hier falsch? Sollte nicht einheitlich sein, oder der Test ist nutzlos?

Answer 1

Nein, es sollte nicht perfekt einheitlich sein. Somit ist das obige kein Beweis für irgendeinen Fehler.

Sie sind zufällig und daher sollte es ziemlich einheitlich sein, aber nicht genau.

Insbesondere würden Sie erwarten, dass jede Zahl ungefähr 10000/50 = 200 mal auftritt - ungefähr mit einer Standardabweichung von sqrt (200), die ungefähr 14 ist - und für 50 Zahlen würden Sie ungefähr 2 Standardabweichungen der Differenz erwarten - was ist + -/28.

Die Abweichung, die durch Verwendung von Modul für RAND_MAX verursacht wird, ist kleiner als das; Sie würden also viel mehr Proben benötigen, um die Verzerrung zu erkennen.

Answer 2

Soweit ich aus http://www.cplusplus.com/reference/random/mersenne_twister_engine/ MT19937 wird leiden unter dem gleichen Bias wie rand()

Die Vorspannung sagen kann, ist aufgrund rand() eine ganze Zahl ohne Vorzeichen in einem gewissen Bereich [0-MAX_RAND] zu erzeugen, wenn Sie nehmen den Modul es kleinere Zahlen etwas wahrscheinlicher macht (es sei denn, Ihr Teiler ein ganzzahliger Teiler von MAX_RAND ist)

Bedenken Sie:

Range [0-74]: 
0 % 50 = 0 
40 % 50 = 40 
50 % 50 = 0 
74 % 50 = 24 
(numbers less than 25 occur twice) 

Answer 3

Sie müssen mehr Proben für eine solche Zufallszahl Tests verwenden. Ich versuchte 50000 mit Ihrem Code, und das Ergebnis ist:

Wie viele Zahlen zu generieren? 50000

Generieren 50000 Nummern von 1 bis? 50

Verwenden Sie rand oder mt19937? [1/2] 2

Anzeigen der 10 häufigsten Zahlen

36 1054 2,108%

14 1051 2,102%

11 1048 2,096%

27 1045 2,09%

2 1044 2,088%

33 1035 2,07%

21 1034 2,068%

48 1034 2,068%

34 1030 2.06%

39 1030 2,06%

Anzeigen der 10 kleinsten gemeinsamen Zahlen

47 966 1,932%

16 961 1,922%

38 960 1,92%

28 959 1.918%

8 958 1,916%

10 958 1,916%

30 958 1,916%

32 958 1,916%

18 953 1,906%

23 953 1,906%