Groupe de travail temps de
mélange et cutoff
Prenons une chaîne de Markov irréductible, apériodique sur un espace
d'état fini. Il est connu (Perron-Frobenius), que la loi de la chaîne
converge vers une unique probabilité invariante à une vitesse
exponentielle, contrôlée par le "trou spectral". On pourrait croire
que l'étude de la convergence s'arrête là. Pourtant, ce résultat est de
nature asymptotique en temps, et néglige la taille de l'espace. Sa
réponse devient inutile lorsqu'on se pose la
question pratique: à quel instant dois-je arrêter ma chaîne si je veux être à
telle distance de la loi invariante ? Un tel instant est appelé un
temps de mélange, et sa définition dépend fortement de la distance
considérée lorsque la taille de l'espace entre en jeu.
On se propose dans le cadre de ce groupe de travail, en partant de
zéro (Perron-Frobenius), de comprendre:
1) les différentes notions de temps de mélange, et les liens qui
existent entre elles (En commençant par les idées de
Lovasz et Winkler, et les livres d'Aldous et Fill (inachevé) et de
Levin, Peres et Wilmer)
2) la problématique du cutoff pour les chaînes de Markov, qui est liée
à la concentration des temps de stationnarité (temps aléatoires auxquels on atteint la loi stationnaire)
3) comment calculer des temps de mélange sur des exemples
(marche aléatoire sur des graphes
aléatoires, dynamique de Glauber dans le modèle de Curie-Weiss,
battage de cartes)
Venez nombreux !
Bruno Schapira et Raphaël Rossignol
Infos pratiques et programme
Le jeudi, salle 117-119 du bâtiment 425 de la fac d'Orsay, à 10h30. Première séance: 29 octobre 2009
| Programme |
| Date | Titre | Orateur |
| 10/06/10 | "Dynamique de Glauber et modèle d'Ising en champ moyen" | A. Le Ny |
| 01/04/10 | "Marche aléatoire simple sur le graphe aléatoire critique d'Erdös-Rényi" | B. Schapira |
| 11/03/10 | "Marche aléatoire simple sur la composante géante du graphe aléatoire d'Erdös-Rényi" | B. Schapira |
| 18/02/10 | "Lovasz et Winkler: les preuves" | R. Rossignol |
| 11/02/10 | "Différents temps de mélange selon Lovasz et Winkler" | R. Rossignol |
| 14/01/10 | "Spectre, fonctions propres et temps de mélange (ch. 13 du livre de Levin, Peres et Wilmer)" | B. Schapira |
| 10/12/09 | "Dualité selon Miclo et Fill" | R. Rossignol |
| 03/12/09 | "Dualité selon Diaconis et Fill" | R. Rossignol |
| 19/11/09 | "Cutoff pour les chaînes de vie et de mort selon Ding, Lubetzky et Peres" | B. Schapira |
| 05/11/09 | "Séparation totale et temps de stationnarité forts" | R. Rossignol |
| Propositions d'exposés |
| Thèmes | Références |
| Dualité | Dossier dualité, en commencant par Diaconis et Fill |
| Cutoff pour les chaînes de vie et de mort | Dossier Birth and Death, articles de Ding, Lubetzky et Peres et de Diaconis et Saloff-Coste |
| Différentes notions de temps de mélange | microsurvey de Lovasz et Winkler et chap. 4 d'Aldous et Fill (dossier Livres et Revues) |
| Temps de mélange pour la dynamique de Glauber sur le modèle de Curie-Weiss | Article de Ding, Lubetzky et Peres (dossier Exemples) |
| Temps de mélange pour la marche élatoire sur la composante géante du graphe aléatoire d'Erdös-Rényi sur-critique | article de Benjamini, Kozma et Wormald (dossier Exemples) |
| Conjecture de Peres: cas non L1 | Dossier ConjecturePeres |
Références
Les références principales sont le livre d'
Aldous et Fill et celui de
Levin, Peres et Wilmer ainsi que le
microsurvey de Lovasz et Winkler.
La plupart des références sont disponibles ici sous forme d'archive zip