Éliminer le biais modulo: comment y parvient-il dans la fonction arc4random_uniform ()?

Le biais modulo est un problème qui survient lorsqu’on utilise naïvement l’opération modulo pour obtenir des nombres pseudo-aléatoires inférieurs à une “limite supérieure” donnée.

Par conséquent, en tant que programmeur C, j’utilise une version modifiée de la fonction arc4random_uniform() pour générer des nombres pseudo-aléatoires répartis de manière uniforme.

Le problème est que je ne comprends pas comment la fonction fonctionne, mathématiquement.

Ceci est le commentaire explicatif de la fonction, suivi d’un lien vers le code source complet:

 /* * Calculate a uniformly dissortingbuted 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

À partir du commentaire ci-dessus, nous pouvons définir:

  • [2^32 % upper_bound, 2^32) – intervalle A
  • [0, upper_bound) – intervalle B

Pour fonctionner, la fonction repose sur le fait que l’intervalle A est mappé sur l’intervalle B.

Ma question est la suivante: mathématiquement, comment se fait-il que les nombres de l’intervalle A correspondent uniformément à ceux de l’intervalle B? Et y a-t-il une preuve pour cela?

Parfois, il est utile de commencer par un exemple facile à comprendre, puis de généraliser à partir de là. Pour simplifier les choses, imaginons que arc4random renvoie uint8_t au lieu de uint32_t , le résultat de arc4random est donc un nombre compris dans l’intervalle [0,256) . Et choisissons une upper_bound de 7.

Notez que 7 ne se divise pas uniformément en 256

 256 = 7 * 36 + 4 

Cela signifie que l’utilisation naïve de l’opération modulo pour obtenir des nombres pseudo-aléatoires inférieurs à 7 aurait pour résultat la dissortingbution de probabilité suivante

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

C’est ce qu’on appelle le biais modulo, les résultats 0,1,2,3 sont plus probables que les résultats 4,5,6.

Pour éviter le biais modulo, nous pourrions simplement rejeter les valeurs 252,253,254,255 et générer un nouveau nombre jusqu’à ce que le résultat se situe dans l’intervalle [0,252) . Tous les nombres dans l’intervalle [0,252) ont une probabilité égale (le rejet de nombres plus élevés n’affecte pas la dissortingbution des nombres les plus bas). Et puisque 7 se divise également en 252, la dissortingbution de probabilité résultante est uniforme

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

C’est essentiellement ce arc4random_uniform fait arc4random_uniform , excepté que arc4random_uniform rejette les nombres arc4random_uniform au bas de la plage. Plus précisément, l’intervalle A serait

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

Après avoir généré un numéro (appelez-le N ) dans l’intervalle [4.256], le calcul final est

 outcome = N % 7 

Il y a 252 nombres dans l’intervalle [4.256) et, puisque 252 est un multiple de 7, chaque résultat de l’intervalle [0,7) a la même probabilité.


C’est ainsi que arc4random_uniform fonctionne, il rejette / tente de nouveau sur une petite plage de nombres et le nombre de nombres dans la plage restante est un multiple de upper_bound. (Comme Upper_bound est généralement un petit nombre comparé à 2 ^ 32, les chances d’avoir plusieurs tentatives pour un seul résultat sont assez petites.)

Mais vous souciez-vous vraiment du biais modulo? Dans la plupart des cas, la réponse est “non”. Considérons notre exemple avec une borne supérieure de 7. La dissortingbution de probabilité pour la mise en œuvre naïve modulo est

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

qui est un biais modulo inférieur à 0,0000002%.

Vous avez donc le choix: soit consacrer une quantité infime de temps à de nouvelles tentatives pour obtenir une dissortingbution parfaite, soit accepter une erreur minuscule dans la dissortingbution de probabilité pour éviter les tentatives.