GdTProbaSDThEr20181126
Temps de mélange de marches aléatoires sur des graphes aléatoires à communautés
Le temps de mélange d’une marche aléatoire sur un graphe connexe fini est intimement lié à la présence de goulots d’étranglement (« bottlenecks ») dans le graphe: intuitivement, plus il est difficile pour la marche de s’échapper de certaines régions du graphe, plus le mélange est lent. De plus, la présence de goulots d’étranglement étroits empêche souvent le cutoff, qui décrit une convergence abrupte à l’équilibre.