Mixing times of Markov chains

Ects : 4

Enseignant responsable :

Volume horaire : 24

Description du contenu de l'enseignement :

How many times must one shuffle a deck of 52 cards? This course is a self-contained introduction to the modern theory of mixing times of Markov chains. It consists of a guided tour through the various methods for estimating mixing times, including couplings, spectral analysis, discrete geometry, and functional inequalities. Each of those tools is illustrated on a variety of examples from different contexts: interacting particle systems, card shuffling, random walks on groups, graphs and networks, etc. Finally, a particular attention is devoted to the celebrated cutoff phenomenon, a remarkable but still mysterious phase transition in the convergence to equilibrium of certain Markov chains.

Compétence à acquérir :

See the webpage of the course.

Mode de contrôle des connaissances :

Final written exam, in class.

Bibliographie, lectures recommandées

See the webpage of the course.

En savoir plus sur le cours