Markov chains and random walks

Outline Assignments References Lectures


From March 25 onwards, we have Zoom available for having the class online at our usual time slot (0900-1300 Wednesdays). If you have not received an email with details, and would like to join, please let me know.

Time: Wednesdays, 0930-1300 (with a total of 30 minutes of break time in the middle)

Place: A-201 Online! (March 25 onwards)


General information

This class is about the use of Markov chains for algorithmic applications. The following is a tentative list of topics I except to cover1:


Basic definitions, convergence notions, Ergodicity, coupling, the “fundamental theorem” of Markov chains

Fast mixing

Coupling and path coupling, spectral methods, conductance, canonical paths.

(Tentatively) Perfect sampling, the Propp-Wilson algorithm


Gibbs measures, Metropolis sampling

Sampling matchings and independent sets in graphs

Connections to approximate counting and phase transitions

Recent progress using high dimensional expanders


  1. Markov chains and mixing times. David A. Levin and Yuval Peres (with contributions from Elizabeth L. Wilmer).

  2. Lectures on finite Markov chains. Laurent Saloff-Coste.

Other courses

The webpage for a previous iteration of this course is available here. The initial few lectures will be virtually identical this time too, but the latter 60% or so of the course will cover different material.


  1. This list will get updated as the course progresses↩︎