Comment fonctionne un générateur de nombres aléatoires, et est-il équitable ?
Lorsque vous appuyez sur « Générer » dans un générateur de nombres aléatoires, un ordinateur, conçu pour suivre des instructions à la lettre, produit quelque chose que personne ne peut prévoir. Ce guide explique comment cela fonctionne, quelle est la façon la plus courante dont un générateur peut être subtilement inéquitable, et comment juger si des résultats sont vraiment aléatoires.
Trois sortes de hasard
Les générateurs pseudo-aléatoires
Un générateur de nombres pseudo-aléatoires (PRNG) est une formule. Il part d'une valeur appelée graine et la transforme encore et encore pour produire une suite qui a l'air aléatoire. Avec la même graine, il reproduit exactement la même suite. C'est utile pour les simulations et les jeux vidéo qui ont besoin de résultats reproductibles.
La fonction Math.random() de JavaScript est un PRNG. Elle convient très bien aux animations et aux jeux sans enjeu. En revanche, les navigateurs ne garantissent pas que sa sortie soit imprévisible, et la spécification n'impose aucun niveau de qualité particulier. Elle ne doit pas servir pour des mots de passe, des tirages au sort avec des lots à la clé, ni pour quoi que ce soit où quelqu'un pourrait tirer profit de deviner le résultat suivant.
Les générateurs cryptographiquement sûrs
Un PRNG cryptographiquement sûr (CSPRNG) est conçu pour que l'observation des sorties précédentes n'aide pas à prédire la suivante. Les systèmes d'exploitation l'initialisent à partir d'événements physiques imprévisibles, comme le bruit de synchronisation du matériel, et continuent d'y injecter de la nouvelle entropie. Dans les navigateurs, il est accessible via la Web Crypto API sous la forme crypto.getRandomValues().
Les générateurs matériels
Un générateur matériel mesure un phénomène physique, comme le bruit électrique, et le convertit en bits. Les processeurs modernes en intègrent un, et les systèmes d'exploitation combinent sa sortie avec d'autres sources pour initialiser leur CSPRNG. La plupart des gens n'ont jamais besoin d'y accéder directement.
Ce qu'utilise Randomify : chaque résultat est tiré de crypto.getRandomValues() dans votre propre navigateur, ce que prennent en charge tous les navigateurs actuels. Les nombres sont générés sur votre appareil, et les listes que vous saisissez ne sont pas envoyées pour produire un résultat.
L'injustice cachée : le biais du modulo
Une source aléatoire fournit des bits, pas « un nombre de 1 à 6 ». C'est lors de la conversion de l'un vers l'autre que beaucoup de générateurs se trompent.
Supposons qu'une source produise un octet aléatoire, un entier de 0 à 255, et qu'un programme ait besoin d'un lancer de dé. Le raccourci consiste à prendre le reste de la division par 6, puis à ajouter 1. Mais 256 n'est pas un multiple de 6 : 256 = 42 × 6 + 4. Les restes 0, 1, 2 et 3 peuvent chacun être obtenus de 43 façons, alors que 4 et 5 ne peuvent l'être que de 42. Les faces 1 à 4 sont donc légèrement plus probables que 5 et 6.
L'écart est faible, 43/256 au lieu de 42/256, mais il s'agit d'un biais systématique et non d'une variation aléatoire. Plus la plage est grande par rapport à la source, plus le biais augmente.
La solution est l'échantillonnage par rejet : on écarte toute valeur brute qui tombe dans le dernier bloc incomplet et on tire à nouveau. Dans l'exemple de l'octet, seules les valeurs de 0 à 251 sont acceptées, si bien que chaque face peut apparaître d'exactement 42 façons. Randomify utilise des valeurs de 32 bits avec échantillonnage par rejet, de sorte que chaque nombre de votre plage a exactement la même probabilité.
Essayez avec la plage de votre choix :
Mélanger équitablement
Tirer des noms dans une liste ou répartir des personnes en équipes exige un mélange équitable : chaque ordre possible doit avoir la même probabilité.
La méthode de référence est le mélange de Fisher–Yates. En partant du dernier élément, on l'échange avec un élément choisi uniformément au hasard parmi ceux qui ne sont pas encore fixés, lui-même compris, puis on recule d'une position. Avec n éléments, chacun des n! ordres possibles est produit avec la même probabilité.
Un raccourci répandu consiste à trier la liste à l'aide de comparaisons aléatoires. Il ne produit pas des ordres équiprobables, et le biais dépend de l'algorithme de tri. Le sélecteur de noms et le générateur d'équipes de Randomify utilisent Fisher–Yates.
Le hasard paraît moins aléatoire qu'on ne le croit
On s'attend souvent à ce qu'une suite aléatoire alterne davantage qu'elle ne le fait en réalité. Une vraie suite aléatoire contient des séries, des regroupements et des répétitions.
| Lancers de pièce équitables | Probabilité d'au moins une série de… | Chance |
|---|---|---|
| 10 | 3 résultats identiques d'affilée | 82,6 % |
| 10 | 4 résultats identiques d'affilée | 46,5 % |
| 100 | 5 résultats identiques d'affilée | 97,2 % |
| 100 | 6 résultats identiques d'affilée | 80,7 % |
| 100 | 7 résultats identiques d'affilée | 54,2 % |
Une série de six « face » sur cent lancers n'est donc pas le signe d'un problème ; c'est son absence qui serait plus surprenante. Il en va de même lorsqu'un générateur de nombres aléatoires renvoie deux fois de suite le même nombre. Avec une plage de 1 à 10, cela arrivera environ une fois sur dix.
Faites l'essai : lancez 100 pièces d'un coup et cherchez la plus longue série.
Comment vérifier qu'un générateur est équitable
Quelques résultats ne suffisent pas à prouver qu'un générateur est équitable, mais vous pouvez repérer les problèmes évidents :
- Rassemblez beaucoup de résultats. Les petits échantillons varient beaucoup. Pour un générateur de 1 à 6, rassemblez des centaines ou des milliers de tirages, pas vingt.
- Comparez les fréquences aux valeurs attendues. Chaque valeur doit apparaître à peu près aussi souvent que les autres. Les statisticiens utilisent un test du khi-deux pour mesurer si les écarts sont plus grands que ce que le hasard produit habituellement.
- Regardez les suites, pas seulement les effectifs. Un générateur pourrait produire des fréquences parfaites en répétant le cycle 1, 2, 3, 4, 5, 6. Vérifiez aussi les répétitions et les séries.
- Demandez comment il fonctionne. Un outil digne de confiance doit indiquer quelle source aléatoire il utilise et comment il la ramène à une plage.
Pour les usages à fort enjeu, comme les clés de sécurité, les tirages encadrés par la loi ou l'échantillonnage scientifique, utilisez un générateur documenté qui respecte la norme applicable et conservez une trace de la procédure.
Questions fréquentes
Le nombre aléatoire d'un ordinateur est-il vraiment aléatoire ? Un CSPRNG est déterministe une fois initialisé, mais il est initialisé à partir d'une imprévisibilité physique, et sa sortie ne peut pas être prédite en pratique sans connaître son état interne. Pour les tirages du quotidien, les jeux et les mots de passe, c'est le bon choix.
Puis-je reproduire un résultat plus tard ? Pas avec un générateur cryptographique, et c'est voulu. Pour qu'un tirage soit vérifiable, enregistrez-le à l'écran ou faites-le devant des témoins, comme décrit dans comment organiser une tombola en ligne équitable.
Pourquoi ai-je obtenu deux fois le même nombre ? Parce que chaque tirage est indépendant. Désactivez l'option « Autoriser les doublons » si vous avez besoin que tous les résultats soient différents, par exemple pour tirer plusieurs gagnants.