Mixing times of Markov chains

ECTS : 6

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 shufflings, 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.
Further information: 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)