Ects : 6

Enseignant responsable :

• JUSTIN SALEZ

Volume horaire : 24

Description du contenu de l'enseignement :

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.

 

Compétence à acquérir :

Pour en savoir plus : www.ceremade.dauphine.fr/~salez/mix.html

Bibliographie, lectures recommandées

Notes de cours, examen 2019 et correction (J. Salez)

Markov Chains and Mixing Times (D. Levin, Y. Peres & E. Wilmer)

Mathematical Aspects of Mixing Times in Markov Chains (R. Montenegro & P. Tetali)

Mixing Times of Markov Chains: Techniques and Examples (N. Berestycki)

Reversible Markov Chains and Random Walks on Graphs (D. Aldous & J. Fill)