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.

• All lectures take place at Université Paris-Dauphine on Mondays, 13:45-17:00, starting from January 29th.
• In order to take the exam, it is mandatory to register for the course by sending an e-mail before March 1 with your name and the name of the university in which you are registered for your Master.
• The exam will take place on March 25th, 14:00-16:00.

• 29.01 - General framework, room B112
• 05.02 - Probabilistic aspects, room B112
• 12.02 - Spectral aspects, room B112
• 26.02 - Geometric aspects 1, room B114
• 04.03 - Geometric aspects 2, room B114
• 11.03 - Variational aspects 1, room B114
• 18.03 - Variational aspects 2, room B112
• 25.03 - Final exam room C311

• Lecture notes (in construction, comments welcome!)
• Exam 2021 and solution
• Exam 2020 and solution
• 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)

• Universality of cutoff for exclusion with reservoirs (Interacting particle systems)
• Cutoff for non-negatively curved Markov chains (Curvature, cutoff).
• Cutoff for the mean-field zero-range process (Interacting particle systems).
• Mixing time of the adjacent walk on the simplex (Continuous state space).
• Cutoff on all Ramanujan graphs (Random walks on graphs, spectral aspects).
• Cutoff phenomena for random walks on random regular graphs (Random walks on random graphs).
• Universality of cutoff for graphs with an added random matching (Random walks on random graphs).
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability (Coupling, Ising model).
• An exposition to information percolation for the Ising model (Coupling, Ising model).
• Trailing the Dovetail Shuffle to its Lair (Card shuffling).
• Path coupling without contraction (Path coupling, curvature).
• The Propp–Wilson algorithm (Perfect sampling, algorithms).
• Mixing times of lozenge tilings and card shuffling Markov chains (Coupling, spectral aspects).