Mélange d'un jeu de cartes : le riffle shuffle
Abstract
Le riffle shuffle (ou dovetail shuffle, ou « mélange à l'américaine ») est une technique bien connue de mélange d'un jeu de cartes, consistant à séparer le paquet en deux parties que l'on entrelace. Ce mémoire étudie cette technique de mélange en s'appuyant sur l'article référence de Dave Bayer et Persi Diaconis (1992). Combien d'itérations sont nécessaires/suffisantes pour que des cartes initialement triées terminent dans un ordre uniforme ou presque ? Si le jeu est mal mélangé, est-il possible d'en tirer un avantage concret en prédisant efficacement l'ordre des cartes ?
Dans un premier temps, nous présentons différentes manières de modéliser le riffle shuffle, ce qui permet notamment de constater que la loi de l'arrangement des cartes après t itérations du mélange n'est pas plus complexe qu'après une seule itération, et nous obtenons une formule explicite pour cette loi.
Notre deuxième section consiste à étudier le temps de mélange pour ce modèle : étant donné epsilon>0, combien d'itérations du riffle shuffle sont nécessaires et suffisantes pour que l'ordre des cartes approche un ordre uniforme à epsilon près ? En notant n le nombre de cartes, on obtient un développement asymptotique en n à l'ordre 2 du temps de mélange. En particulier, celui-ci est équivalent à (3/2)*log_2(n) : cet équivalent est indépendant de la précision epsilon souhaitée, on dit qu'on a cutoff.
Enfin, notre troisième partie apporte un résultat nouveau par-rapport à l'article d'origine. Intuitivement, un jeu mal mélangé est un jeu dont un observateur avisé peut prédire l'ordre des cartes plus facilement que s'il était parfaitement uniforme. Bayer et Diaconis décrivent une stratégie conjecturée comme optimale pour deviner les cartes successives d'un jeu mélangé par riffle shuffle avec feedback. Nous réfutons cette conjecture par un contre-exemple, mais montrons qu'une partie du raisonnement est valable et nécessaire à l'optimalité.
Fichier principal
Mélange d'un jeu de cartes, le riffle-shuffle.pdf (1.66 Mo)
Télécharger le fichier
Origin | Files produced by the author(s) |
---|