QUAND UN MÉLANGE À LA MAIN OUBLIE-T-IL LE PAQUET ?
Mélanger des cartes est une version concrète d’une question de base en probabilités : combien de temps un processus aléatoire met-il à oublier son point de départ ? Un paquet neuf est rangé. Chaque mélange le brouille un peu plus, jusqu’à ce qu’aucune trace de l’ordre initial ne soit détectable.
Les mathématiciens distinguent deux niveaux de réponse. Le temps de mélange donne l’ordre de grandeur. Un seuil (« cutoff ») en dit bien plus : autour d’un instant précis, le paquet bascule de « nettement pas mélangé » à « parfaitement mélangé » presque d’un coup. Mélangez un peu moins et on peut encore le voir ; un peu plus et on ne peut plus.
Le mélange, vu par un mathématicien
Dans le mélange à la main (« overhand shuffle »), on tient le paquet dans une main et on fait tomber de petits tas de cartes dans l’autre. L’article le modélise ainsi : chacun des n − 1 interstices entre cartes voisines est coupé indépendamment avec une probabilité p, et l’ordre des tas obtenus est inversé. Un passage complet sur le paquet compte pour un mélange.
Selon l’article, des travaux antérieurs avaient déjà cerné l’ordre de grandeur. Pemantle avait encadré le temps de mélange entre n² et n² log n ; Jonasson a ensuite montré que n² log n est le bon ordre. Mais la constante exacte, et l’existence même d’un seuil net, restaient ouvertes : Diaconis et Pal ont listé le seuil du mélange à la main comme problème ouvert en 2022.
Le résultat
Yunjiang Jiang démontre que le seuil existe et le situe.
Théorème. Pour une probabilité de coupe p fixée, le mélange à la main mélange le paquet, au premier ordre, en
p² / (2(1 − p)π²) × n² log n
mélanges. Un peu avant, le paquet reste loin du hasard ; un peu après, il en est proche.
Pour p = 1/2 — une coupe dans la moitié des interstices en moyenne — la formule devient n² log n / (4π²).
Comment marche la preuve
La preuve a trois parties indépendantes.
- La borne inférieure suit une seule carte. Sa position évolue de façon remarquablement nette : des motifs exacts en forme de cosinus décroissent à un rythme connu, même pour un paquet fini. Additionnés sur tout le paquet, ils gardent une trace détectable de l’ordre de départ jusqu’à l’instant prédit.
- La borne supérieure compare deux paquets qui ne diffèrent que par l’échange de deux cartes. Avec les mêmes coupes aléatoires, la différence se comporte comme deux positions marquées qui errent dans le paquet jusqu’à devenir voisines et pouvoir fusionner. Le rythme auquel cela arrive correspond à la borne inférieure.
- Une inégalité statique sur les permutations, sans rapport avec le mélange, transforme cette comparaison en énoncé sur le paquet entier. C’est la partie la plus technique de l’article, construite par récurrence sur des tableaux qui comptent comment les cartes se répartissent entre des blocs.
L’article démontre aussi un seuil pour une autre façon de mesurer le désordre, l’entropie relative, sans en fixer la position exacte.
Ce que la formule dit d’un vrai paquet
Avec un paquet de 52 cartes et p = 1/2, la formule donne 52² × ln 52 / (4π²), environ 270 mélanges. C’est notre propre calcul, pas un chiffre de l’article, et il faut le lire comme une indication grossière : le théorème décrit le comportement de très grands paquets, et le terme correctif n’est pas chiffré. Pour comparaison, l’article cite l’échelle de (3/2) log₂ n établie par Bayer et Diaconis pour le mélange « riffle » — environ 8,6 pour 52 cartes, avec la même réserve. L’écart entre n² log n et log n est ce qui rend le mélange à la main si lent.
Premier ordre, mains idéalisées
Le résultat est au premier ordre : il ne donne ni la largeur de la fenêtre de transition ni sa forme exacte. La probabilité de coupe est fixée, et les coupes sont supposées indépendantes, une idéalisation des vraies mains. Dans une note, l’auteur indique que le système d’IA GPT-6 Astra a été « utilisé pour développer des arguments, vérifier des calculs et préparer l’exposé », et que l’auteur reste responsable du contenu mathématique. L’article est un preprint.