COL863: Special Topics in Theoretical Computer Science
Topic: Rapid Mixing in Markov Chains
II semester: 2021-22
Amitabha Bagchi
Class Timings: TBA.
Venue: TBA.
Course objectives
The purpose of this course is to discuss the mathematical tools and techniques required for theoretically analysing the time taken for a Markov Chain to converge to its steady state distribution.
Topics
Basic properties of Markov Chains; Some useful Markov Chains; Random walks; Markov Chain Monte Carlo (including Metropolis and Glauber dynamics chains); Total Variation Distance and Mixing; Coupling; Strong stationary times; Random walks on networks; Hitting times and Cover times; Algebraic view of Markov chains; the Transportation Metric and Path Coupling.
Background required: Elementary probability, some graph theory, linear algebra.
Texts
- D. A. Levin, Y. Peres, and E. Wilmer, Markov Chains and Mixing Times. Download here (Please download the 2nd edition). This book will be refered to as LPW on the rest of this page.
- D. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph. 1999-2002. Available here.
Important: You are expected to have familiarised yourself with the material in Appendix A and read through Chap 1 of LPW before the first meeting of this class.
Course outline
All Chapter numbers refer to LPW. The bullet points in italics will be largely self-study.
- Intro to Finite Markov Chains (Chap 1).
- Classical Markov Chains (Chap 2).
- Random Walks on Networks (Chap 9), Hitting Times (Chap 10) and Cover Times (Chap 11).
- Intro to Markov Chain Mixing (Chap 4) and Coupling (Chap 5).
- Lower Bounds on Mixing Times (Chap 7).
- Eigenvalues of Markov Chains (Chap 12) and Comparison of Chains (Chap 13)
- The Transportation Metric and Path Coupling (Chap 14).
- Evolving Sets (Chap 17).
Refresher texts
Evaluation
Evaluation will be on the basis of 3-4 take-home exams.
Amitabha
Bagchi