Analysis of Markov chains
Lecture notes
20171127. Hidden Markov models and the Kálmán filter.
20171123. Coupling from the past (contd.).
 Notes are extremely rough!
20171119. Rejection sampling and importance sampling. Sampling DNF solutions. Coupling from the past.
20171116. Strong stationary times.
 See the textbook.
20171112. The AndersenPeres method for local sparse cuts.
20171109. Review of martingales and evolving sets.
20171106. The AndersenPeres method for local sparse cuts.
20171102. Doob \(h\)transform and the volume biased evolving set process.
 See Chapter 17 in the textbook.
20171030. Evolving set process as a tool for analysis: mixing time and conductance.
 See Chapter 17 in the textbook.
20171026. Martingales and optional stopping theorems. Evolving set process and local sparsest cut.
20171023. The JerrumSinclairVigoda algorithm for approximating the permanent.
 See also the paper.
20171012 (B). Brief description of the JerrumSinclairVigoda approach for approximating the permanent.
 See also the paper.
20171012 (A). Counting matchings when the number of nearperfect matchings is not too large.
20171005. Counting perfect matchings using the JerrumSinclair chain. Log concavity of matching counts.
20170928. Canonical paths for the JerrumSinclair chain (continued). Sampling vs. counting for the monomerdimer model.
 See also book chapter by Mark Jerrum.
20170925. Sampling from the monomerdimer model. The JerrumSinclair (Metropolis) chain. Canonical paths for the JerrumSinclair chain.
 See book chapter by Mark Jerrum.
20170921. Multicommodity flow and the spectral gap. The canonical path method. Simple examples: Hypercube random walk and the random transpoitions chain.
 Notes scribed by Ramprasad.
20170918. Conductance and the spectral gap. Easy side of Cheeger’s inequality.
20170914. Spectral gap and expander mixing lemma. Conductance and the Laplacian.
20170911. Spectral methods. Spectrum of the hypercube random walk, tight analysis of mixing time for the hypercube random walk.
20170907. Glauber dynamics for the Ising model on bounded degree graphs, relationship with correlation decay.
20170904. More on path coupling: Glauber dynamics for independent sets.
20170831. Sampling colorings in bounded degree graphs, path coupling.
20170828. Mixing time lower bound for the hypercube. Reversible chains, heat bath dynamics.
20170817. Coupling and mixing times, random walk on the hypercube.
20170815. Irreducibility and aperiodicity, coupling, dual of the total variation distance.
20170810. Linear algebraic proof of the “fundamental theorem”.
20170807. 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:"LightGraphs", "IJulia", "QuantEcon", "PyPlot", "LaTeXStrings"]) do (x) map([ 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 SaloffCoste.
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 cover^{1}:
 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 ProppWilson 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↩︎