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.


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.


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.

Refresher texts


Evaluation will be on the basis of 3-4 take-home exams.
Amitabha Bagchi