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.
- Code, HTML Output.
  
  To run the code, you need to install julia and jupyter, along with the following julia packages: LightGraphs, IJulia, QuantEcon, PyPlot and LaTeXStrings. Once you have julia up and running, theses packages can be installed by running the following command on the julia 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 cover¹:

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 1~~ April 8, Wednesday (in class).

This list will get updated as the course progresses↩︎