SMF

Exposé Bourbaki 1219 : Phénomène de cutoff pour les chaînes de Markov à courbure positive (d'après Justin Salez)

Exposé Bourbaki 1219 : Cutoff phenomenon for Markov chains with positive curvature (after Justin Salez)

Anna BEN HAMOU
Exposé Bourbaki 1219 : Phénomène de cutoff pour les chaînes de Markov à courbure positive (d'après Justin Salez)
  • Consulter un extrait
  •  
                
  • Année : 2024
  • Tome : 454
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 60J27
  • Pages : 375-392
  • DOI : 10.24033/ast.1236

Une chaîne de Markov présente le phénomène de cutoff si sa distance à l’équilibre reste proche de $1$ jusqu’à un certain temps, puis chute abruptement vers $0$ en un temps bien plus court. Découvert dans les années 1980 dans le contexte des mélanges de cartes, ce phénomène a depuis été observé pour une très grande variété de chaînes. Cependant, le problème de l’identification des mécanismes sous-jacents au cutoff reste une des plus grandes questions dans le domaine des temps de mélange. À cet égard, l’article Cutoff for non-negatively curved Markov chains de Justin Salez constitue une avancée majeure. Premièrement, il établit un critère très général pour le cutoff, reposant sur la notion de varentropie, permettant de comprendre le cutoff comme un phénomène de concentration entropique. Deuxièmement, il montre que ce critère est vérifié pour une grande famille de chaînes: les chaînes à courbure positive satisfaisant une condition qui ne concerne que les ordres de grandeur des temps de mélange et de relaxation.

A Markov chain exhibits the cutoff phenomenon if its distance to equilibrium remains close to $1$ until a certain time, then falls abruptly towards $0$ in a much shorter time. Discovered in the 1980s in the context of card shuffles, this phenomenon has since been observed for a very wide variety of chains. However, the problem of identifying the mechanisms underlying the cutoff remains one of the key questions in the field of mixing times. In this respect, the article Cutoff for non-negatively curved Markov chains by Justin Salez is a major breakthrough. Firstly, he establishes a very general criterion for the cutoff, based on the notion of varentropy, making it possible to understand the cutoff as a phenomenon of entropic concentration. Secondly, he shows that this criterion is verified for a large family of chains: chains with positive curvature satisfying a condition that only involves the orders of magnitude of the mixing and relaxation times.

Chaînes de Markov, temps de mélange, cutoff, courbure, varentropie
Markov chains, mixing times, cutoff, curvature, varentropy

Électronique
Electronic
Prix public Public price 10.00 €
Prix membre Member price 7.00 €
Quantité
Quantity
- +