COL863: Special Topics in Theoretical Computer Science
Topic: Rapid Mixing in Markov Chains

II semester: 2016-17

Amitabha Bagchi

Class Timings: Mon Wed 11AM, Th 12PM.
Room: LH 520.


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


There will be a self-study viva held in the 2nd week of the class (the week of 9-13 Jan) to determine the extent of preparation for the course. This will count for 20% of the grade. Those students who score below 50% in this exam will be advised to withdraw the class.

The remaining 80% will be given on the basis of 3-4 take-home exams.


Exam guidelines

Amitabha Bagchi