Cours de M2 - Temps de mélange (année 2020)

Résumé

Combien de fois faut-il battre un paquet de 52 cartes pour que la permutation aléatoire obtenue soit à peu près uniformément distribuée ? Ce cours est une introduction sans pré-requis à la théorie moderne des temps de mélange des chaînes de Markov. Un interêt particulier sera porté au célèbre phénomène de "cutoff", qui est une transition de phase remarquable dans la convergence de certaines chaînes vers leur distribution stationnaire. Parmi les outils abordés figureront les techniques de couplage, l'analyse spectrale, le profil isopérimétrique, ou les inégalités fonctionnelles de type Poincaré. En guise d'illustration, ces méthodes seront appliquées à divers exemples classiques issus de contextes variés: mélange de cartes, marches aléatoires sur les groupes, systèmes de particules en intéraction, algorithmes de Metropolis-Hastings, etc. Une place importante sera accordée aux marches sur graphes et réseaux, qui sont aujourd'hui au coeur des algorithmes d'exploration d'Internet et sont massivement utilisées pour la collecte de données et la hiérarchisation des pages par les moteurs de recherche.

Tous les cours ont lieu le lundi de 13h45 à 17h, à l'Université Paris-Dauphine.

Examen

Voici le sujet 2020, mis en ligne le lundi 27 avril à 14h00. Les copies scannées doivent m'être envoyées le même jour, avant 16h00 précises. Seuls les étudiants inscrits au cours peuvent passer l'examen.

Bibliographie

Programme détaillé

Sujets de mémoire