Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 22 mai 2018 à 14h00 en B107, Anna Ben Hamou nous parlera de : Temps de mélange de marches aléatoires sur des graphes aléatoires

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 : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr