Markov chains and random walks
Announcement:
From March 25 onwards, we have Zoom available for having the class online at our usual time slot (09001300 Wednesdays). If you have not received an email with details, and would like to join, please let me know.
Time: Wednesdays, 09301300 (with a total of 30 minutes of break time in the middle)
Place: A201 Online! (March 25 onwards)
Lectures
20200513, 20200520. (Transcript of class held using video conferencing). The local sparsest cut problem.
20200506. (Transcript of class held using video conferencing). Introduction to filtrations, stopping times and martingales. Strong stationary times.
20200422, 20200429. (Transcript of classes held using video conferencing). Perfect sampling. ProppWilson algorithm. Importance sampling.
20200401, 20200411, 20200412, 20200415. (Transcript of classes held using video conferencing.) Uniform sampling of spanning trees. Uniform sampling of matroid bases. Modified log Sobolev inequalities for the basisexchange walk. Connections with strongly log concave polynomials.
20200325. (Transcript of class held using video conferencing. Please let me know if you find any errors.). Modified log Sobolev inequality for the Boolean hypercube. Introduction to matroids: linear and graphic matroids. Bases of matroids.
20200318. (Notes posted online: Optional Google Hangouts discussion on Sunday, 2PM5PM). Detailed review of functional inequalities and continuous time. Modified log Sobolev inequality in a simple case.
20200304. Expander graphs. The connection between spectral and combinatorial definitions. Expander mixing lemma. Markov chains in continuous time; the “semigroup” representation. Rates of change of variance and relative entropy. Mixing times and modified log Sobolev inequalities.
20200226. Applying the multicommodity flow and canonical methods to lowerbound the spectral gap of the monomerdimer Glauber dynamics.
20200219. Dirichlet form and the spectral gap. Proving Poincare inequalities via lowcongestion multicommodity flows; the canonical path method; application to the hypercube random walk. The monomerdimer model.
20200212. Spectrum of reversible Markov chains, and mixing times. Mixing time for the hypercube random walk using the spectral gap. Tight bounds on the hypercube random walk using the full spectrum.
20200205. Path coupling. Glauber dynamics for independent sets and proper colourings.
20200129. The Coupling lemma. Mixing time bounds using coupling. Reversibility of Markov chains. Glauber dynamics and the MetropolisHastings sampler.
20200122. Lectures 1 and 2. Introduction, total variation distance, simulations. Linear algebraic proof of the “fundamental theorem”
Note that the proof of the “fundamental theorem” we did in class was slightly differently structured and shorter.

To run the code, you need to install
julia
andjupyter
, along with the followingjulia
packages:LightGraphs
,IJulia
,QuantEcon
,PyPlot
andLaTeXStrings
. Once you havejulia
up and running, theses packages can be installed by running the following command on thejulia
prompt:"LightGraphs", "IJulia", "QuantEcon", "PyPlot", "LaTeXStrings"]) do (x) map([ Pkg.add(x)end
Once you have installed the above software, you can run the command
jupyter notebook
in the directory in which the above files lie, and
jupyter
will open a tab in your browser where you can interactively run the code.
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 cover^{1}:
 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 ProppWilson algorithm
 Sampling
Gibbs measures, Metropolis sampling
Sampling matchings and independent sets in graphs
Connections to approximate counting and phase transitions
Recent progress using high dimensional expanders
References
Markov chains and mixing times. David A. Levin and Yuval Peres (with contributions from Elizabeth L. Wilmer).
Lectures on finite Markov chains. Laurent SaloffCoste.
Other courses
 Constantinos Daskalakis’s course
 Shayan Oveis Gharan’s course
 Dana Randall’s course  See this course specially for many interesting statistical physics connections that we will not get to in our course.
 Alistair Sinclair’s course
 Eric Vigoda’s course
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.
Assignments
 Homework 1. Due
April 1April 8, Wednesday (in class).
This list will get updated as the course progresses↩︎