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.
- See the textbook.
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.
- See Chapter 17 in the textbook.
2017-10-30. Evolving set process as a tool for analysis: mixing time and conductance.
- See Chapter 17 in the textbook.
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.
- See also the paper.
2017-10-12 (B). Brief description of the Jerrum-Sinclair-Vigoda approach for approximating the permanent.
- See also the paper.
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.
- See also book chapter by Mark Jerrum.
2017-09-25. Sampling from the monomer-dimer model. The Jerrum-Sinclair (Metropolis) chain. Canonical paths for the Jerrum-Sinclair chain.
- See book chapter by Mark Jerrum.
2017-09-21. Multi-commodity flow and the spectral gap. The canonical path method. Simple examples: Hypercube random walk and the random transpoitions chain.
- Notes scribed by Ramprasad.
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.
-
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.
-
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.
Assignments
- Homework 4. Due December 3, Sunday.
- Homework 3. Due November 5, Sunday.
- Homework 2. Due October 5, Thursday.
- Homework 1. Due August 27, Sunday.
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
This list will get updated as the course progresses↩︎