Mixing Times of Markov Chains

Term 2, 2020

Course description

Worksheet 1 with hints

Worksheet 1 without hints

Solutions to Worksheet 1

Worksheet 2 (Due March 19th)

Solution to worksheet 2

Slides for first lecture

Notes on hit-mix relations, characterization of cutoff in terms of hitting times, and characterization of cutoff for trees.

Notes on hitting times from equilibrium (contained in previous pdf)

Notes on cover times and random walk on lamplighter graphs

Notes on Coupling from the past and the Ising model

Notes on evolving sets

Lecture notes by Perla Sousi (will be edited and expanded by me throughout the term).

Notes by Nathanael Berestycki (some typos corrected; last updated on Feb 12th 2019).

I will mostly follow the 2nd edition of the book Markov Chains and Mixing Times by David Levin and Yuval Peres with contributions by Elizabeth Wilmer Available on Levin's website.

Another good textbook (with an emphasis on analytic techniques) is the book Mathematical Aspects of Mixing Times of Markov chains by R. Montenegro and P. Tetali.