Mélange d'un jeu de cartes : le riffle shuffle - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance
Master Thesis Year : 2018

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
Vignette du fichier
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)

Dates and versions

dumas-03168533 , version 1 (13-03-2021)

Identifiers

  • HAL Id : dumas-03168533 , version 1

Cite

Florian Galliot. Mélange d'un jeu de cartes : le riffle shuffle. Probabilités [math.PR]. 2018. ⟨dumas-03168533⟩

Collections

DUMAS MEM-UNIV-SU
629 View
573 Download

Share

More