Partant d’une chaîne de Markov donnée sur un espace fini, de loi stationnaire uniforme, Chatterjee et Diaconis (2020) ont proposé la perturbation suivante visant à accélérer le mélange: on se donne une permutation sur l'espace d'états et l'on considère la chaîne qui alterne entre des sauts aléatoires gouvernés par la chaîne initiale, et des sauts déterministes gouvernés par la permutation. Ces auteurs ont montré que si la permutation vérifie une condition d'expansion par rapport à la chaîne initiale, alors le temps de mélange de la chaîne permutée est logarithmique en la taille de l'espace, et que cette condition est vérifiée par presque toutes les permutations. Dans cet exposé, nous verrons que l'on peut même caractériser très précisément le temps de mélange: pour presque toutes les permutations, la chaîne permutée présente un cutoff, en un temps qui ne dépend que du taux d'entropie de la chaîne initiale.
