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: Monday, Wednesday, Friday 12:00-1:00 (tentatively).

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

Text: TBD. There also will be papers and lecture notes added to the website throughout the course.

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