Résumé : Dans cet exposé, nous commencerons par rappeler la notion de temps de mélange d'une chaîne de Markov et introduirons le phénomène de cutoff, qui décrit une convergence très abrupte à l'équilibre. Établir le cutoff pour une chaîne donnée requiert souvent une analyse extrêmement fine, et il existe assez peu de résultats généraux permettant par exemple d'exhiber des grandes classes de graphes sur lesquels la marche aléatoire présente le cutoff. On peut alors se demander ce qu'il se passe sur un graphe « typique ». Nous considérerons le cas des graphes aléatoires à suite prescrite de degrés, et montrerons qu'avec forte probabilité, sur de tels graphes, la marche aléatoire simple et la marche aléatoire dite « sans rebroussement » présentent le cutoff. En interprétant les temps de mélange comme des entropies limites sur un arbre de Galton-Watson qui constitue une approximation locale du graphe, nous montrerons de plus que la marche aléatoire sans rebroussement mélange plus vite que la marche simple. Ces résultats sont issus de collaborations avec Justin Salez (Paris Diderot), Eyal Lubetzky (NYU) et Yuval Peres (Microsoft Research).

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr