Convergence and Mixing Times of Markov Chains
This is a specialized topics course for advanced undergraduates and graduate students. It focuses on the theory of mixing times—the core metric that quantifies how fast a Markov chain converges to its stationary distribution.
We will develop the basic theory and some of the main techniques and tools from probability, geometry and spectral theory used to estimate mixing times. These tools will be applied to analyze several chains of interest.
We will develop the basic theory and some of the main techniques and tools from probability, geometry and spectral theory used to estimate mixing times. These tools will be applied to analyze several chains of interest.
讲师
日期
2026年02月27日 至 06月19日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周五 | 09:50 - 12:15 | Shuangqing | ZOOM 07 | 559 700 6085 | BIMSA |
修课要求
An undergraduate level understanding of linear algebra and probability. It is desirable that the audience has taken at least one semester of graduate probability. It is also recommended that the audience take the course “Probability 2” by Yuval Peres in parallel with this course, which will discuss general aspects of Markov chains
课程大纲
A review of finite Markov chains
Basic Properties of Mixing Times
Coupling of Markov chains
-Bounding Total Variation Distance
-Strong Stationary Times
-Path Coupling
Spectral Techniques for Reversible Markov Chains
-Spectral Decomposition
-Spectral Gap and Relaxation Time
Geometric Bounds
-Dirichlet Form and Variational Characterisation of Spectral Gap
-Canonical Paths and Comparison of Chains
-Bottleneck Ratio and Cheeger’s inequality
Martingale method and the Evolving Set
Lower Bounds on Mixing Times and the Cutoff Phenomenon
-Counting and Diameter Bounds
-Distinguishing Statistics and Wilson’s method
-Examples of Cutoff
Random Walks on Groups and the Upper Bound Lemma*
Basic Properties of Mixing Times
Coupling of Markov chains
-Bounding Total Variation Distance
-Strong Stationary Times
-Path Coupling
Spectral Techniques for Reversible Markov Chains
-Spectral Decomposition
-Spectral Gap and Relaxation Time
Geometric Bounds
-Dirichlet Form and Variational Characterisation of Spectral Gap
-Canonical Paths and Comparison of Chains
-Bottleneck Ratio and Cheeger’s inequality
Martingale method and the Evolving Set
Lower Bounds on Mixing Times and the Cutoff Phenomenon
-Counting and Diameter Bounds
-Distinguishing Statistics and Wilson’s method
-Examples of Cutoff
Random Walks on Groups and the Upper Bound Lemma*
参考资料
Primary Textbook: Markov Chains and Mixing Times, second edition by David A. Levin and Yuval Peres with contributions by Elizabeth Wilmer. PDF is available on Levin's website.
Useful Supplementary Texts & Notes:
Ravi Montenegro and Prasad Tetali. Mathematical Aspects of Mixing Times in Markov Chains. (With an emphasis on analytic methods)
Sébastien Roch. Modern Discrete Probability: An Essential Toolkit.
Nathanaël Berestycki. Mixing Times of Markov Chains: Techniques and Examples. [https://homepage.univie.ac.at/nathanael.berestycki/?page_id=184]
Useful Supplementary Texts & Notes:
Ravi Montenegro and Prasad Tetali. Mathematical Aspects of Mixing Times in Markov Chains. (With an emphasis on analytic methods)
Sébastien Roch. Modern Discrete Probability: An Essential Toolkit.
Nathanaël Berestycki. Mixing Times of Markov Chains: Techniques and Examples. [https://homepage.univie.ac.at/nathanael.berestycki/?page_id=184]
听众
Advanced Undergraduate
, Graduate
视频公开
不公开
笔记公开
公开
语言
中文
, 英文
讲师介绍
Shuo Qin has been the first Chern Instructor at BIMSA. He obtained a Ph.D. in mathematics in 2024 from New York University under the supervision of Prof. Pierre Tarrès. His work is in probability theory, especially in random processes with memory or reinforcement.