• Libellé inconnu,

Séminaire MODAL'X :Anna Ben Hamou (LPSM, Sorbonne Université)

Publié le 6 février 2022 Mis à jour le 25 mai 2022

Cutoff pour les chaînes de Markov permutées

Date(s)

le 2 juin 2022

14h10-15h10
Lieu(x)
Bâtiment Allais (G), salle 614 B
Plan d'accès
Résumé : Il arrive souvent qu'une chaîne de Markov "naturelle" sur un espace d'états fini soit très lente à converger. Dans le cas d'une mesure stationnaire uniforme, Chatterjee et Diaconis (2020) ont proposé la perturbation suivante: on se donne une permutation sur l'espace d'états et l'on considère la chaîne qui alterne entre des sauts aléatoires gouvernés par la chaîne initiale, et des sauts déterministes gouvernés par la permutation. Ces auteurs ont montré que si la permutation vérifie une condition d'expansion par rapport à la chaîne initiale, alors le temps de mélange de la chaîne permutée est logarithmique en la taille de l'espace, et que cette condition est vérifiée par presque toutes les permutations. Dans cet exposé, nous verrons que l'on peut même caractériser très précisément le temps de mélange: pour presque toutes les permutations, la chaîne permutée présente un cutoff, en un temps qui ne dépend que du taux d'entropie de la chaîne initiale.

Mis à jour le 25 mai 2022