Analysis of Markov chains

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.

• Paper

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

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

• Paper

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.

• See Chapter 17 in the textbook, and the Anderson-Peres paper.

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.