Analysis of Markov chains

Outline Assignments References Notes

Lecture notes

References

  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.

Assignments

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:

Fundamentals

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

Sampling

Gibbs measures, Metropolis sampling

Sampling matchings and independent sets in graphs

Connections to approximate counting and phase transitions

Other topics

Evolving sets and local sparsest cuts


  1. This list will get updated as the course progresses