# 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 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)
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

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.

### Other courses

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).

1. This list will get updated as the course progresses↩︎