Mini-Course: Mixing Time Analysis for MCMC Algorithms

Markov chain Monte Carlo (MCMC) is one of the most widely used methods for sampling from high-dimensional probability distributions, with applications in machine learning, statistics, and data science. Understanding the convergence rate of MCMC algorithms, which is captured by the concept of mixing time, is a central topic in MCMC theory. In this 3-day mini-course, I will introduce several classical and modern techniques for analyzing the mixing time of standard MCMC algorithms. The course will include the following topics:

Lecture 1 (4:00 pm Jan 15): Markov chains, mixing times, and coupling analysis (lecture notes)
Lecture 2 (2:00 pm Jan 16): Spectral gaps and comparisons of Markov chains (lecture notes)
Lecture 3 (9:30 am Jan 17): Down-up walks and spectral independence (lecture notes)

Location: 中国科学技术大学高新校区 GT-B110

Prerequisites: Probability Theory and Linear Algebra.

Resources

For further reading, I recommend the following books and lecture notes. For classical techniques such as coupling and spectral analysis, one can refer to the following three books.

David A. Levin, Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times
Mark Jerrum, Counting, sampling and integrating: algorithms and complexity
Ravi Montenegro and Prasad Tetali, Mathematical Aspects of Mixing Times in Markov Chains

For the more recent developments on spectral independence, one can refer to the following lecture notes.

Daniel Štefankovič and Eric Vigoda, Lecture Notes on Spectral Independence and Bases of a Matroid: Local-to-Global and Trickle-Down from a Markov Chain Perspective

There are many excellent courses on Markov chains and sampling algorithms. Here are some of them.