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.

• Lectures take place at Université Paris-Dauphine on Mondays 12:00-15:15, starting from September 16th.
• The exam will take place on December 9th, 10:00-12:00 in room C212.

• 16.09 - General framework, room B128
• 17.09 - Probabilistic aspects 1, room B506
• 18.09 - Probabilistic aspects 2, room B108
• 23.09 - Spectral aspects, room B107
• 30.09 - Geometric aspects 1, room B504
• 14.10 - Geometric aspects 2, room B107
• 04.11 - Variational aspects 1, room C214
• 18.11 - Variational aspects 2, room B107

• 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).