Topics in the study of Markov chains

Time: Mondays and Thursdays, 1600-1730.

Place: Online lectures. YouTube playlist. Student presentations in A-201/A-237.

Student presentation topics

Lecture notes/transcripts

General information

This is a two credit course. The initial half (about 20 hours) is a regular lecture course, comprising an introduction to Markov chains. After this part, the second half will be a “reading-course” comprise student presentation exploring various current topic of interest in the subject. The introductory lectures will be a selection from the following topics (since this is a reading course, the list may change based on how the course progresses):

  1. The fundamental theorem of Markov chains. Canonical examples of Markov chains: Glauber dynamics and the Metropolis sampler, Random walks of graphs (especially the Boolean hypercube), etc.

  2. Coupling and associated methods for bounding mixing times: examples from hypercube random walks and Glauber dynamics.

  3. Spectral methods and combinatorial methods for bounding the spectral gap. Examples: Ferromagnetic Ising model, Matching in general graphs.

  4. Recent progress using high dimensional expanders and its connection with the geometry of polynomials.

  5. An introduction to Markov chains on continuous state spaces. Sampling from convex bodies.

Aside from this, I also plan to cover a selection (based on interest) from the following list of tentative topics.

  1. Coupling and algorithms for “perfect sampling”: the Propp-Wilson algorithm (including results on perfect sampling of colourings by TIFR students!).

  2. Sharper mixing time bounds from log Sobolov inequalities and hypercontractivity. Connections with concentration of measure.

  3. Local algorithms: the evolving set Markov chain and its use in finding local sparse cuts

  4. Concentration inequalities for Markov chains.


In addition to undergraduate algorithms and discrete mathematics, the only other prerequisites to be some familiarity with linear algebra (the notions of eigenvalues, eigenvectors and eigenvalue decompositions) and analysis (notions of convergence, norms, Hölder’s inequality etc.).


For the initials part of the reading course, the book Markov chains and mixing times by Galvin, Peres and Witmer, and the monograph Lectures on finite Markov chains by Saloff-Coste will be useful. We will refer to original papers as needed.


Evaluation will be based on 3 homework assignments (70% of the final grade) and a final exam (30% of the final grade). Total number of meeting hours are expected to be about 30. However, since this is partly a reading course, participating students might have to prepare and give a few lectures towards the end of the course, and in general would also have to prepare in advance for the material to be discussed in each meeting.

Other courses

The webpage for a previous lecture version of this course is available here. The initial few lectures will be virtually identical this time too, but I expect to cover a different selection of the more “advanced” material this time.