# Analysis of Markov chains

## Lecture notes

• 2017-11-27. Hidden Markov models and the Kálmán filter.

• 2017-11-23. Coupling from the past (contd.).

• Notes are extremely rough!
• 2017-11-19. Rejection sampling and importance sampling. Sampling DNF solutions. Coupling from the past.

• 2017-11-16. Strong stationary times.

• 2017-11-12. The Andersen-Peres method for local sparse cuts.

• 2017-11-09. Review of martingales and evolving sets.

• 2017-11-06. The Andersen-Peres method for local sparse cuts.

• 2017-11-02. Doob $$h$$-transform and the volume biased evolving set process.

• 2017-10-30. Evolving set process as a tool for analysis: mixing time and conductance.

• 2017-10-26. Martingales and optional stopping theorems. Evolving set process and local sparsest cut.

• 2017-10-23. The Jerrum-Sinclair-Vigoda algorithm for approximating the permanent.

• 2017-10-12 (B). Brief description of the Jerrum-Sinclair-Vigoda approach for approximating the permanent.

• 2017-10-12 (A). Counting matchings when the number of near-perfect matchings is not too large.

• 2017-10-05. Counting perfect matchings using the Jerrum-Sinclair chain. Log concavity of matching counts.

• 2017-09-28. Canonical paths for the Jerrum-Sinclair chain (continued). Sampling vs. counting for the monomer-dimer model.

• 2017-09-25. Sampling from the monomer-dimer model. The Jerrum-Sinclair (Metropolis) chain. Canonical paths for the Jerrum-Sinclair chain.

• 2017-09-21. Multi-commodity flow and the spectral gap. The canonical path method. Simple examples: Hypercube random walk and the random transpoitions chain.

• 2017-09-18. Conductance and the spectral gap. Easy side of Cheeger’s inequality.

• 2017-09-14. Spectral gap and expander mixing lemma. Conductance and the Laplacian.

• 2017-09-11. Spectral methods. Spectrum of the hypercube random walk, tight analysis of mixing time for the hypercube random walk.

• 2017-09-07. Glauber dynamics for the Ising model on bounded degree graphs, relationship with correlation decay.

• 2017-09-04. More on path coupling: Glauber dynamics for independent sets.

• 2017-08-31. Sampling colorings in bounded degree graphs, path coupling.

• 2017-08-28. Mixing time lower bound for the hypercube. Reversible chains, heat bath dynamics.

• 2017-08-17. Coupling and mixing times, random walk on the hypercube.

• 2017-08-15. Irreducibility and aperiodicity, coupling, dual of the total variation distance.

• 2017-08-10. Linear algebraic proof of the “fundamental theorem”.

• 2017-08-07. Introduction, total variation distance, simulations.

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

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

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

Other topics

Evolving sets and local sparsest cuts

1. This list will get updated as the course progresses