CS 8803 MCM: Markov Chain Monte Carlo Algorithms
Special Topics Course, Spring 2010

Markov chains, or random walks on graphs, are fundamental tools used for approximation algorithms, counting algorithms, combinatorial optimization and estimating various quantities associated with a large combinatorial set. They arise in applications from statistical physics, biology, economics, web analysis, vision, and across many other scientific disciplines.

In this course we will examine how Markov chains can be used in algorithms and we will study methods for making these algorithms provably efficient. There will be a special focus on problems arising from statistical physics and how insights from computing, mathematics and physics have contributed to many recent breakthroughs.

Time: Wednesday and Friday 12:00-1:30.

Prerequisites: A graduate course in probability theory and a graduate course in algorithms.

Useful references:

• Draft of chapters 12 and 13 of Mertens and Moore (handed out in class).
• Mark Jerrum's book, with chapters near the bottom of the webpage.
• David Aldous and Jim Fill's book draft
• Book by Levin, Peres and Wilmer (Sorry, this one you would have to order. It's excellent for the more formal analysis of Markov chains.)
• A tutorial giving a very brief overview of the topics in the course.

Lectures:

• January 11, 13: Exact counting. Gessel-Viennot and counting matchings on a lattice
• January 15: The Matrix-tree theorem (MM 252-254)
• January 20: Pfaffian orientations and counting matchings in planar graphs(MM 787-789)
• January 22: Introduction to Markov chains (MM 652-655)
• January 27: Spectral gap (MM 671-673)
  • Not yet proofed: Lecture notes (Note: I'm including first drafts of the notes in case it might be helpful to any of you for the homework, etc. These will be improved (and perhaps corrected) over time.)
• January 29: Measuring convergence rate for walks on the hypercube and the Riffle shuffle (MM 655-659)
  • Not yet proofed: Lecture notes
• February 3: Coupling (Mark Jerrum's notes)
  • Not yet proofed: Lecture notes
• February 5: Sampling random colorings (MM 659-570)
• February 10: Path Coupling (See Jerrum's book (link above) - chapter 4.)
• February 12: Path Coupling (cont), linear extensions of a partial order, spanning trees
• February 14: Sampling lattice configuations: tilings and 3-colorings. (The original paper)
  • Notes: Part 1 Part 2 Part 3
• February 17: Spanning trees (Jerrum's book -- chapter 4)
• February 19: Coupling from the past (See Eric Vigoda's notes)
• February 24 and 26: Conductance, congestion and canonical flows (Jerrum's book -- Chapter 5)
• March 3, 5: Sampling matchings and perfect matchings in dense graphs
• March 10: Estimating the partition function for matchings and approximately counting k-colorings
• March 12: Estimating the permanent (and sampling matchings in any bipartite graph)
• March 17: Almost uniform sampling and approximate counting (Notes)
• March 19: Glauber dynamics on the Ising model: Fast and Slow results
  • See Levin, Peres, Wilmer book or Randall: Slow mixing via topological obstructions
• March 31: Sampling Ising states via the High Temp Exp and the Random Cluster Model
  • Jerrum and Sinclair: Estimating the partition function
  • Randall and Wilson: Sampling spin configurations
• April 2: The comparison method
  • Randall, Tetali: Comparison method for analyzing Glauber dynamics
• April 7: Decomposition method
  • Page 5-7 in Paper by Jerrum, Son, Tetali and Vigoda
• April 9: Metropolis Coupled MCMC / Simulated Tempering
• April 14: TBA
• April 16: TBA
• April 21, 23: Estimating the volume of a convex body: Guest lecturer Daniel Dadush
  • Vempala's survey
• April 28, 30: Student presentations

Short projects:
Please read one of the following papers and write a short (3-4) page summary of the results and the main ideas. You will have the opportunity to give a 20 minute summary to the class the last week of classes. You can work along or in groups of 2.

• Dyer, Sinclair, Vigoda, Weitz: Mixing in time and space
  
• Gore, Jerrum: The Swendsen-Wang process does not always mix rapidly.
  
• Gkantsidis, Mihail, Saberi: Conductance and congestion in power law graphs
  
• Hayes: A simple condition implying rapid mixing of single-site dynamics on spin systems
  
• Lovasz and Winkler: Stopping rules to bound mixing rates
  
• Bhatnagar, Randall: Slow mixing of simulated tempering on the Potts model
  
• Hayes, Sinclair: Lower bounds on mixing rates
  
• Goldberg, Martin, Paterson: Strong spatial mixing for lattice graphs with fewer colors
  
• Morris, Peres: Bounding mixing with evolving sets
  
• Wilson: Upper and lower bounds for sampling lozenge tilings (or even paths)
  
• Randall, Sinclair: Testable algorithms for sampling self-avoiding walks
  
• Dyer, Frieze, Jerrum: Counting independent sets in sparse graphs
  
• Weitz's deterministic approximate counting algorithm for independent sets - Linji Yang

Open problems / Projects (optional):

• 1. Generalize the idea of topological obstructions (fault lines) for showing slow mixing to higher dimensions.
  • Randall: slow mixing of Glauber for Independent sets in 2 dimensions
  • Thomas: mass gap proof for Ising in higher dimensions
• 2. We can sample 3 colorings (Luby, Randall, Sinclair) and 6 or greater colors (Goldberg, et al., Molloy et. al, Jerrum, etc) and Z^2. What about 4 and 5 colors? Could simulations help??
• 3. Suppose that we have a coupling proof that certain block dynamics are prapidly mixing, but coupling apparently fails for single-site dynamics. Are there conditions when we can use the block dynamics to determine a (crazy) distance function to show that single-site dynamics are efficient.
• 4. To be continued....

Course Outline:

• Classical exact counting algorithms
  
  • Spanning Trees using Kirchoff's Matrix Tree Theorem
    
  • Kasteleyn's polynomial-time algorithm for the permanent of a planar graph
    
  • Gessel-Viennot's algorithm for counting perfect matchings in lattice graphs
    
  
  
• Complexity class # P, and showing that the permanent is #P-complete
  
  
• Connections between approximate counting and sampling
  
  
• Markov chain fundamentals
  • Ergodic Markov chains and the stationary distribution
    
  • Convergence times
    
  • Coupling
  
  
• Coupling from the past and exact sampling techniques
  
  
• Bounding mixing times using coupling
  • Random spanning trees
    
  • Path coupling techniques
    
  • random colorings
  
  
• Advanced coupling techniques
  • Random lozenge tilings
    
  • Generating random linear extensions of a partial order
    
  • Random colorings and non-Markovian coupling
  
  
• Spectral methods
  • Canonical paths
    
  • Generating a random matching
    
  • Conductance
  
  
• Approximating the permanent of a non-negative matrix
  
  
• Indirect methods
  • The comparison method
    
  • Decomposition
  
  
• Statistical physics
  • Ising model
    
  • Connections between phase transitions and fast/slow mixing of Glauber dynamics
    
  • Slow mixing for the Ising model and independent sets
    
  • Strong spatial mixing and very fast mixing of Glauber dynamics
  
  
• Couting/sampling algorithms for the Ising model
  • Approximating the partition function via the high-temperature expansion
    
  • Random sampling via the random-cluster expansion
  
  
• Approxiate couting via dynamic programming
  • Dyer's knapsack result
  
  
• Estimating the volume of a convex body
  
  
• Sampling contingency tables
  
  
• Metropolis-coupled MCMC
  
  
• Optional topics
  • Weitz's deterministic algorithm for approximately counting independent sets
    
  • Bayesian inference
    
  • Phylogenetic tree reconstruction
    
  • Stopping rules for sampling
    
  • Sampling in real spaces