Qu'est-ce que je fais de mal avec ces nombres aléatoires?

Question

On m'a dit que rand() mod n produit des résultats biaisés, donc j'ai essayé de faire ce code pour le vérifier. Il génère s numéros de 1 à l et les trie par occurrences.

#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; 
     } 
    } 
} 

Après l'exécution de ce code, je peux repérer le biais attendu de rand():

$ ./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 Je reçois à peu près le même résultat avec mt19937 et uniform_int_distribution! Quel est le problème ici? Ne devrait pas être uniforme, ou le test est inutile?

Answer 1

Non, il ne devrait pas être parfaitement uniforme. Ainsi, ce qui précède n'est pas la preuve d'une erreur.

Ils sont aléatoires et devraient donc être assez uniformes, mais pas exactement. En particulier, vous vous attendez à ce que chaque nombre se produise environ 10000/50 = 200 fois - approximativement avec un écart type de 200 sqrt (environ 200) - et pour 50 nombres vous attendez environ 2 écarts-types de différence - qui est + -/28.

La polarisation provoquée par l'utilisation du module pour RAND_MAX est plus petite que celle; Vous aurez donc besoin de beaucoup plus d'échantillons pour détecter le biais.

Answer 2

Pour autant que je peux dire de http://www.cplusplus.com/reference/random/mersenne_twister_engine/ mt19937 souffrira de la même biais que rand()

Le biais est rand due() générant un entier non signé dans une plage [0-MAX_RAND], lorsque vous prendre le module rend plus petit nombre un peu plus probable (à moins que votre diviseur est un diviseur entier de MAX_RAND)

Considérez:

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

Answer 3

Vous devez utiliser plusieurs échantillons pour ces tests de nombres aléatoires. J'ai essayé 50000 avec votre code, et le résultat est:

Combien de nombres à générer? 50000

Générer 50000 nombres allant de 1 à? 50

Utilisez rand ou mt19937? [1/2] 2

Afficher les 10 numéros les plus courants

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%

Afficher les 10 moins numéros communs

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%