Comment mélanger une liste pour que tous les ordres soient vraiment équiprobables ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En programmant un jeu de cartes en NSI, j'ai écrit un mélange qui me semblait évident : pour chaque carte, l'échanger avec une carte tirée au hasard. En comptant les résultats sur des millions de mélanges d'un petit jeu, j'ai vu que certains ordres sortaient plus souvent que d'autres. J'ai voulu comprendre ce biais et trouver le bon algorithme.

L'enjeu et les notions du programme

Utiliser le dénombrement pour démontrer qu'un algorithme naturel est biaisé et qu'un autre est exactement uniforme.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Mélanger une liste de $n$n éléments, c'est choisir l'une des $n!$n! permutations. Un bon mélange doit les rendre toutes équiprobables : chacune doit sortir avec la probabilité $\frac{1}{n!}$1/n!. Problématique : quel algorithme le garantit ?

2. 2. Mathématiques : compter les issues

   4 min

   Mélange naïf : pour $i$i de 0 à $n-1$n-1, échanger l'élément $i$i avec un élément d'indice $j$j tiré parmi les $n$n. Il y a $n$n tirages à $n$n issues : $n^n$nⁿ déroulements équiprobables. Pour que les $n!$n! permutations soient équiprobables, il faudrait que chacune soit obtenue par le même nombre de déroulements, donc que $n!$n! divise $n^n$nⁿ.

   Pour $n=3$n=3 : $3^3=27$3³=27 déroulements et $3!=6$3!=6 permutations. Or 6 ne divise pas 27 (27 est impair). Le biais est donc certain. Le décompte exact donne trois ordres obtenus 5 fois et trois ordres obtenus 4 fois : probabilités $\frac{5}{27}\approx 0,185$5/27≈0,185 et $\frac{4}{27}\approx 0,148$4/27≈0,148, au lieu de $\frac{1}{6}\approx 0,167$1/6≈0,167.

   Fisher-Yates : pour $i$i de $n-1$n-1 à 1, échanger l'élément $i$i avec un élément tiré parmi les indices 0 à $i$i. Nombre de déroulements : $n\times (n-1)\times \cdots \times 2=n!$n×(n-1)×…×2=n!. Chaque déroulement donne une permutation différente, donc chaque permutation est obtenue exactement une fois : probabilité $\frac{1}{n!}$1/n!.

3. 3. NSI : vérifier par simulation

   3 min

   En Python, on mélange un million de fois la liste [0, 1, 2] et l'on compte chaque ordre avec un dictionnaire. Avec la méthode naïve, les fréquences se répartissent autour de 0,185 et 0,148 ; avec Fisher-Yates, toutes sont proches de 0,167.

   La fonction random.shuffle utilise Fisher-Yates. Un biais de mélange a déjà eu des conséquences réelles : un site de poker en ligne a été attaqué à la fin des années 1990 parce que son mélange (et son générateur) ne produisait qu'une petite partie des ordres possibles.

4. 4. Conclusion

   1,5 min

   Le mélange naïf produit $n^n$nⁿ issues, que l'on ne peut pas répartir également entre $n!$n! ordres : il est biaisé. Fisher-Yates produit exactement $n!$n! issues, une par ordre : il est uniforme. Un dénombrement suffit à démontrer l'équité d'un algorithme. J'ouvre sur le mélange des cartes à la main, où il faut environ sept battements pour bien mélanger un jeu.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Croire qu'un algorithme qui « mélange beaucoup » est forcément uniforme.
• Oublier que n^n issues équiprobables ne se répartissent pas toujours également.
• Tirer j parmi tous les indices dans Fisher-Yates.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Algorithmique et Python (Première spé maths) →

Autres questions : hasard et simulation

• Comment un ordinateur, machine parfaitement déterministe, peut-il produire du hasard ?
• Comment simuler un dé à six faces équitable avec une simple pièce de monnaie ?
• Peut-on obtenir un tirage parfaitement équitable avec une pièce truquée dont on ignore le biais ?
• Après n pas faits au hasard, à quelle distance de son point de départ se trouve-t-on ?

Toutes les questions maths-nsi →