Markov chains and random walks
Announcement:
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)
Lectures
2020-05-13, 2020-05-20. (Transcript of class held using video conferencing). The local sparsest cut problem.
2020-05-06. (Transcript of class held using video conferencing). Introduction to filtrations, stopping times and martingales. Strong stationary times.
2020-04-22, 2020-04-29. (Transcript of classes held using video conferencing). Perfect sampling. Propp-Wilson algorithm. Importance sampling.
2020-04-01, 2020-04-11, 2020-04-12, 2020-04-15. (Transcript of classes held using video conferencing.) Uniform sampling of spanning trees. Uniform sampling of matroid bases. Modified log Sobolev inequalities for the basis-exchange walk. Connections with strongly log concave polynomials.
2020-03-25. (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.
2020-03-18. (Notes posted online: Optional Google Hangouts discussion on Sunday, 2PM-5PM). Detailed review of functional inequalities and continuous time. Modified log Sobolev inequality in a simple case.
2020-03-04. 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.
2020-02-26. Applying the multi-commodity flow and canonical methods to lower-bound the spectral gap of the monomer-dimer Glauber dynamics.
2020-02-19. Dirichlet form and the spectral gap. Proving Poincare inequalities via low-congestion multi-commodity flows; the canonical path method; application to the hypercube random walk. The monomer-dimer model.
2020-02-12. 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.
2020-02-05. Path coupling. Glauber dynamics for independent sets and proper colourings.
2020-01-29. The Coupling lemma. Mixing time bounds using coupling. Reversibility of Markov chains. Glauber dynamics and the Metropolis-Hastings sampler.
2020-01-22. 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:map(["LightGraphs", "IJulia", "QuantEcon", "PyPlot", "LaTeXStrings"]) do (x) 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 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
-
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 Saloff-Coste.
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↩︎