Temps de mélange et phénomène de cutoff pour la marche aléatoire sur des grands graphes aléatoires

Le cutoff est une transition de phase remarquable dans la convergence de certaines chaînes de Markov vers leur loi stationnaire: la distance à l'équilibre passe brutalement de 1 à 0 lorsque le nombre d'itérations approche une valeur critique appelée temps de mélange. Découvert dans le contexte du mélange de cartes (Aldous-Diaconis, 1986), ce phénomène est désormais rigoureusement établi pour de nombreuses chaînes réversibles. Dans cet exposé, je ferai une longue introduction au sujet, puis je présenterai des résultats obtenus avec Charles Bordenave et Pietro Caputo dans le cadre non-réversible des marches aléatoires sur des grands graphes dirigés aléatoires.