Mélanger est plus dur qu'il n'y paraît : un million de tirages du mélange en une ligne

Un million de mélanges de quatre éléments

Quatre éléments ont vingt-quatre ordres. C'est assez petit pour être compté exhaustivement, et c'est ce qui en fait le bon cas de test : lance un mélange un million de fois, compte la fréquence de chacun des vingt-quatre, et un mélange équitable doit mettre environ 41 667 dans chaque case. Tout ce qui favorise systématiquement certains ordres apparaîtra comme une bosse, et un seul nombre — le khi-deux — condense la table entière en un verdict. À 23 degrés de liberté, une méthode équitable tourne autour de 23, et tout ce qui dépasse 27,32 arriverait moins de 5 % du temps par pur hasard.

L'écriture en une ligne a marqué 125 397. Pas 30, pas 300 — cinq mille fois le seuil. L'ordre le plus fréquent, BADC, est sorti 62 810 fois ; le plus rare, DBCA, 30 998 fois. L'ordre initial ABCD a survécu intact 62 485 fois, soit moitié plus souvent qu'il ne devrait. Le même million passé par un Fisher-Yates correctement écrit a produit 10,3, ce à quoi ressemble une méthode équitable : les extrêmes étaient 41 434 et 41 879, un écart d'environ 1 %. Étendre le test à cinq éléments creuse encore l'écart — 229 683 contre 89,0 — car chaque élément supplémentaire donne à l'algorithme de tri une décision de plus à mal prendre.

Pas vingt-quatre probabilités, mais deux

Les comptes ne sont pas éparpillés. Triés, ils forment deux grappes serrées : huit ordres autour de 62 500 et seize autour de 31 250. Ce sont exactement 1/16 et 1/32 d'un million, et l'arithmétique boucle — 8 × (1/16) + 16 × (1/32) = 1. Quatre millions de tirages supplémentaires ont testé directement cette hypothèse et donné un khi-deux de 19,7 à 23 degrés de liberté, soit un bon ajustement. Le mélange en une ligne sur ce moteur n'est donc pas approximativement uniforme avec un tremblement : c'est une distribution à deux valeurs où la moitié de la masse de probabilité est tassée dans un tiers des résultats.

Les huit ordres favorisés partagent une propriété à noter : ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC et DBAC gardent tous C hors des deux premières positions. Ce n'est pas de la mystique, c'est l'algorithme de tri qui transparaît. Un tableau de quatre éléments est court, donc V8 ne quitte jamais son chemin d'insertion binaire ; le comparateur est appelé 4,5 fois en moyenne, et 4,5 tirages à pile ou face ne peuvent pas produire 24 résultats équiprobables, car 24 ne divise aucune puissance de deux. Le biais est inscrit dans la forme de l'arbre de décision avant même que le hasard n'intervienne.

Le biais appartient au moteur, pas au langage

ECMA-262 exige que la fonction de comparaison passée à sort soit un comparateur cohérent : transitif, antisymétrique, et rendant la même réponse pour la même paire à chaque fois. Un comparateur bâti sur Math.random casse les trois en un seul appel. La réponse de la spécification n'est pas de définir ce qui se passe, mais de dire que si le comparateur est incohérent, le résultat du tri est défini par l'implémentation. Cette seule phrase dit tout. Tu n'as pas écrit un mélange aux statistiques inhabituelles — tu as écrit un programme dont la norme refuse de spécifier la sortie.

Conséquence pratique : ces comptes mesurent un moteur à une version donnée, pas une constante universelle. V8 a changé son tri plus d'une fois ; une exécution sur un autre moteur, ou sur le même après mise à jour, produira une autre distribution bosselée, et un tableau assez long pour déclencher le chemin de fusion en produira encore une autre. Rien dans la norme ne l'interdit, et rien ne te prévient quand cela arrive. Un mélange dont les propriétés statistiques bougent quand on patche le moteur d'exécution n'est pas un mélange testable.

Fisher-Yates, et l'erreur d'indice qui le ruine

L'algorithme correct — l'algorithme P de Knuth — parcourt le tableau du dernier indice jusqu'au deuxième, et à chaque position i tire un indice j uniformément entre 0 et i inclus, puis échange les positions i et j. Trois détails portent toute la démonstration. La boucle descend. Le tirage inclut i lui-même, donc un élément a le droit de rester en place. Et l'intervalle rétrécit d'un cran à chaque itération, si bien que le nombre de chemins d'exécution vaut n × (n−1) × … × 2 = n!, soit exactement le nombre de permutations. Une bijection entre chemins d'exécution et résultats, c'est la définition de l'uniformité, et elle vaut pour tout n, pas seulement ceux que tu as testés.

Change un caractère et tout casse. La variante courante parcourt le tableau vers le haut et tire j sur le tableau entier à chaque fois, ce qui semble plus aléatoire et ne l'est pas. Cette version a n^n chemins d'exécution, et n^n n'est jamais un multiple de n! au-delà de n = 2 : certaines permutations sont donc atteignables par plus de chemins que d'autres. Mesurée sur le même million de tirages, elle a marqué 29 913 — mille fois le seuil, avec l'ordre le plus fréquent à 58 698 et le plus rare à 31 233. C'est la plus dangereuse des deux erreurs, précisément parce qu'elle ressemble à la version du manuel et passe tous les contrôles à l'œil.

Le biais du modulo : la deuxième façon de tordre un mélange

Fisher-Yates a besoin d'un entier uniforme dans un intervalle, et la façon évidente d'en tirer un d'une valeur aléatoire de 32 bits est de prendre le modulo de la taille de l'intervalle. Ce n'est uniforme que si l'intervalle divise exactement 2^32. En général non : 2^32 modulo 52 vaut 48, donc 48 des 52 résultats reçoivent une préimage de plus que les quatre autres. À 32 bits, l'excès qui en résulte tourne autour du millionième de pour cent et personne ne le verra jamais. Réduis la source à un seul octet et la même arithmétique devient brutale : 256 modulo 52 vaut encore 48, mais cette fois 48 résultats obtiennent 5 préimages et 4 n'en obtiennent que 4 — un excès de 25 %, visible en quelques milliers de tirages.

Le correctif est l'échantillonnage par rejet, et il ne coûte presque rien. Calcule le plus grand multiple de l'intervalle qui tient dans ta source — pour un tirage 32 bits et un intervalle de 52, c'est 2^32 moins 48 — retire dès que la valeur dépasse cette borne, et ne prends le modulo que des valeurs acceptées. La zone de rejet fait 48 valeurs sur 4 294 967 296, donc le nombre attendu de tirages supplémentaires est d'environ un sur quatre-vingt-dix millions. Tu paies une comparaison par appel et tu achètes l'uniformité exacte : le meilleur échange de tout cet article.

Math.random n'est pas un mélangeur de cartes

Même un Fisher-Yates parfait reste limité par le générateur en dessous. Un jeu de 52 cartes a 52! ordres, soit 8,07 × 10^67, ou environ 2^225,6. Le générateur derrière Math.random dans V8 porte 128 bits d'état interne : il ne peut donc atteindre au plus que 2^128 ≈ 3,4 × 10^38 ordres de jeu — une fraction de 4,2 × 10^-30 du total. L'écrasante majorité des mélanges d'un jeu standard n'est tout simplement pas productible, quel que soit le nombre d'appels. C'est un plafond mathématique dur, pas un défaut d'implémentation, et il s'applique à tout générateur pseudo-aléatoire dont l'état est plus petit que l'espace à couvrir.

Deux autres propriétés comptent en pratique. Math.random n'est ni initialisable ni reproductible : la spécification n'offre aucun moyen de fixer un point de départ, et elle exige explicitement que des realms distincts produisent des séquences distinctes ; un bug vu une fois ne peut donc pas être rejoué. Et il n'est pas imprévisible au sens cryptographique — un observateur qui voit assez de sorties peut reconstruire l'état et prédire la suite. Si quelqu'un peut gagner à deviner ton mélange — une tombola, un tirage doté, un jeton de sécurité, tout ce qui est mélangé devant un public — utilise crypto.getRandomValues, avec l'échantillonnage par rejet par-dessus. Si le mélange est un plan de table ou un quiz d'entraînement, Math.random avec un Fisher-Yates correct convient parfaitement.

Questions fréquentes

Trier avec un comparateur aléatoire est-il toujours biaisé, ou seulement dans certains navigateurs ?

Toujours biaisé, mais différemment partout. La norme exige un comparateur cohérent et déclare le résultat défini par l'implémentation quand elle n'en obtient pas ; chaque moteur — et chaque version de chaque moteur — produit donc sa propre distribution bosselée. Sur Node 26.3.0, le cas à quatre éléments s'effondre sur deux probabilités seulement, 1/16 pour huit ordres et 1/32 pour les seize autres, ce qu'un test de quatre millions de tirages confirme avec un khi-deux de 19,7 à 23 degrés de liberté. Un autre moteur ne te donnera pas ces chiffres exacts : il te donnera d'autres chiffres faux. C'est pire qu'un biais connu et fixe, car il n'y a rien de stable à tester et une mise à jour du moteur d'exécution peut changer les statistiques de ton tirage sans changer une ligne de ton code.

Comment écrire Fisher-Yates pour qu'il soit réellement correct ?

Commence au dernier indice et descends jusqu'à l'indice 1. À chaque position i, tire j uniformément entre 0 et i inclus, puis échange les éléments en i et j. Trois choses doivent être justes en même temps : la boucle descend, le tirage inclut i lui-même, et l'intervalle rétrécit d'un cran à chaque itération. Réunis les trois et le nombre de chemins d'exécution vaut exactement n factorielle, un par permutation, ce qui rend la sortie uniforme pour toute longueur de tableau et pas seulement pour celles que tu as testées. La variante qui monte et tire j sur tout le tableau à chaque fois est l'erreur classique : elle a n puissance n chemins, jamais multiple de n factorielle au-delà de n = 2, et elle a mesuré un khi-deux de 29 913 sur le test à quatre éléments où un mélange équitable tourne autour de 23.

Ai-je besoin de crypto.getRandomValues, ou Math.random suffit-il ?

Le test tient en une question : quelqu'un pourrait-il gagner à prédire le résultat ? Mélanger des questions de quiz, placer une classe, randomiser l'ordre d'exercices : Math.random dans un Fisher-Yates correct convient, et la différence ne se verra jamais. Tirer un lot, choisir un échantillon d'audit, générer quoi que ce soit qui se comporte comme un jeton : utilise crypto.getRandomValues, car Math.random est un générateur pseudo-aléatoire dont l'état interne se reconstruit à partir d'une série modeste de sorties, après quoi toute valeur future est prévisible. Il y a une seconde raison, plus discrète. Un jeu de 52 cartes a environ 2^225,6 ordres et le générateur de V8 porte 128 bits d'état : il n'atteint donc au mieux qu'un ordre de jeu sur 10^30. Ce plafond tient à la taille de l'état, pas à la qualité de l'algorithme.

Qu'est-ce que le biais du modulo, et quand compte-t-il ?

C'est ce qui arrive quand on comprime un intervalle qui ne divise pas ta source. Prends une valeur aléatoire de 32 bits, réduis-la modulo 52 : tu obtiens un nombre de 0 à 51, mais 2^32 divisé par 52 laisse un reste de 48, donc 48 de ces résultats reçoivent une valeur source de plus que les quatre autres. À 32 bits, l'excès qui en découle avoisine le millionième de pour cent — réellement négligeable. La même arithmétique sur une source de 8 bits est un autre animal : 256 modulo 52 vaut aussi 48, mais cette fois les résultats favorisés reçoivent 5 valeurs sources et les autres seulement 4, un excès de 25 % que quelques milliers de tirages révèlent. Le correctif est l'échantillonnage par rejet : rejeter tout tirage égal ou supérieur au plus grand multiple de l'intervalle tenant dans ta source, ce qui pour 32 bits et un intervalle de 52 écarte 48 valeurs sur 4,29 milliards, environ un tirage sur quatre-vingt-dix millions.

Comment tester mon propre mélange sans bagage en statistiques ?

Réduis le problème jusqu'à pouvoir tout compter. Prends un tableau de quatre éléments, mélange-le un million de fois, et tiens le compte de chacun des vingt-quatre ordres — un dictionnaire indexé sur la chaîne concaténée suffit. Regarde ensuite deux nombres : le plus grand compte divisé par le plus petit, et le compte de l'ordre initial non mélangé. Un mélange équitable donne un rapport proche de 1,01 à cette taille d'échantillon et laisse l'ordre initial autour de 1 sur 24. Dans les mesures présentées ici, Fisher-Yates a donné 1,011 et le tri en une ligne 2,026, l'ordre intact apparaissant 50 % plus souvent qu'il ne devrait. Tu n'as pas besoin du khi-deux pour voir cet écart ; le khi-deux te dit seulement à quel point il est impossible, et 125 397 contre un seuil de 27,32 est à peu près aussi impossible qu'une mesure peut l'être.