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

- Notes are
**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.**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.

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