Phénomène de cutoff pour des marches aléatoires sur des graphes aléatoires

Jeudi 14 avril 2016 14:00-15:00 - Anna Ben-Hamou - LPMA

Résumé : On dit qu’une chaîne de Markov ergodique à espace d’états fini présente le phénomène de cutoff lorsque sa distance à l’équilibre reste très proche de 1 jusqu’au temps de mélange, puis chute abruptement vers 0 en une période de temps bien plus petite, appelée la fenêtre du cutoff. Dans cet exposé, nous considérerons des marches aléatoires « non-backtracking » (sans marche arrière) sur des graphes aléatoires à degrés prescrits. Sous une condition générale de sparsité, nous établirons le cutoff, sa fenêtre, et montrerons que le profil de la distance converge vers une forme universelle, celle de la fonction de queue gaussienne. Il s’agit d’un travail en collaboration avec Justin Salez.

Phénomène de cutoff pour des marches aléatoires sur des graphes aléatoires  Version PDF