Voici comment mélanger des cartes à la perfection

Inutile de rechercher le mélange parfait si on veut jouer dans la soirée

Lorsque le paquet est neuf, les cartes sont dans un ordre déterminé : si on les distribue telles quelles, tous les joueurs savent exactement quelles cartes ont été distribuées à qui.

En mélangeant le paquet, on crée un ordre aléatoire des cartes. On dira alors qu’un paquet de cartes est « parfaitement mélangé » si tous les ordres possibles ont la même probabilité. Une manière d’atteindre cet objectif est d’étaler les cartes sur une table et d’en choisir une au hasard qui deviendra la première carte du paquet ; d’en choisir une deuxième au hasard que l’on placera en deuxième position ; d’en choisir une troisième au hasard que l’on placera en troisième position, etc. Cette technique possède un intérêt théorique, mais n’est pas très pratique si on est pressé de jouer.

Pour une partie amicale, l’objectif n’est pas tant d’obtenir un mélange « parfait », mais un mélange « suffisamment bon » : si l’on mélange trop peu le paquet, un observateur avisé pourra reconnaître certaines successions de cartes (qui auront été mal mélangées) et s’en servir à son avantage. Si en revanche le paquet est suffisamment bien mélangé, même le joueur le plus entraîné ne pourra pas distinguer de structure dans la suite de cartes : on aura l’illusion d’un mélange parfait.

Pour déterminer si un mélange est suffisamment bon, les mathématiciens introduisent une notion de distance par rapport au mélange parfait (basée sur les probabilités des différents ordres possibles) : plus cette distance est proche de zéro, plus le mélange est proche du mélange parfait ; si la distance est élevée, le paquet est mal mélangé.

Le cœur du problème : comment mélanger un paquet de cartes

L’une des méthodes les plus efficaces est celle du mélange américain : il s’agit de couper le paquet en deux à un endroit aléatoire et de regrouper les deux paquets en intercalant leurs cartes respectives.

Dave Bayer et Persi Diaconis ont montré qu’en partant d’un paquet de cartes complètement ordonné, six mélanges américains mélangent très mal le paquet, mais huit suffisent largement pour être proche d’un mélange parfait.

Les autres façons de battre les cartes sont-elles plus efficaces que le mélange américain ? La réponse est non : par exemple, avec un mélange « standard » (appelé mélange français), il vous faudra répéter l’opération environ 10 000 fois pour obtenir un jeu bien mélangé…

Un paquet bien mélangé restera bien mélangé

Ces résultats, aussi frappants soient-ils, pourraient paraître anecdotiques. Détrompez-vous. Ils font partie d’un pan important de recherche lancé dans les années 80, qui étudie les « temps de mélange » de processus aléatoires.

L’idée est que de nombreux processus aléatoires possèdent un état d’équilibre vers lequel ils tendent. Par exemple, lorsqu’un paquet de cartes est parfaitement mélangé, il reste parfaitement mélangé si l’on bat les cartes : le mélange parfait est un état d’équilibre vers lequel on tend lorsque l’on bat les cartes.

De manière générale, la question est de savoir au bout de combien de temps le système sera proche de l’état d’équilibre si l’on part d’un état quelconque. En pratique, cela permet de déterminer combien de temps laisser tourner certains algorithmes informatiques basés sur des processus aléatoires.

Voici un exemple concret : pour explorer de grands réseaux (réseaux sociaux, Internet, etc.), des algorithmes aléatoires sont utilisés, notamment afin d’identifier les nœuds du réseau possédant beaucoup de connexions (influenceurs, sites Internet de référence, etc.). La question de savoir quel est le temps nécessaire pour que ces algorithmes identifient correctement les hubs du réseau est alors centrale.

Mélanger plus de 6 fois est indispensable, mais au-delà de 8, c’est inutile : d’où vient cette transition abrupte ?

L’exemple du mélange des cartes montre qu’il y a une transition abrupte : moins de 6 mélanges et le paquet est mal mélangé, plus de 8 et il l’est presque parfaitement. Ce phénomène a été mis en évidence dans de nombreux processus aléatoires, qui s’approchent d’un état d’équilibre non pas de manière progressive, mais de manière abrupte.

La compréhension des mécanismes de ce phénomène de transition abrupte est un enjeu important de recherche : même si cela est bien compris dans de nombreux exemples spécifiques, il n’existe pas encore de théorie générale permettant d’expliquer ce phénomène ou de prédire pour quels systèmes il a lieu. Pour expliquer comment une transition abrupte est possible, une idée approximative est que certains ingrédients doivent se mettre en place – cette mise en place peut être longue et rester peu détectable, si les ingrédients concernent chacun une petite partie du système. Une fois ces ingrédients en place, leur combinaison peut alors entraîner un basculement rapide du système.

En guise de conclusion, notons qu’il y a 52 ! = 52x51x50… 4x3x2x1 ordres possibles des cartes : il y a 52 choix pour la première carte du paquet, puis il reste 51 choix pour la deuxième, puis 50 pour la troisième, etc. Ce nombre est environ 10⁵² (un 1 suivi de 52 zéros) fois le nombre de secondes écoulées depuis le début de l’univers… Ainsi, si vous mélangez suffisamment bien votre jeu de cartes, il est extrêmement vraisemblable que l’ordre précis que vous avez obtenu apparaisse pour la première fois dans l’histoire de l’univers !

Quentin Berger, Associate professor, Sorbonne Université

Cet article est republié à partir de The Conversation sous licence Creative Commons. Lire l’article original.