CS 7535: Markov Chain Monte Carlo Algorithms
Fall 2014

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: Tuesday and Thursdsay 12:00-1:30.

Location: ES&T L1118 Prerequisites: A graduate course in probability theory and a graduate course in algorithms.

TA: Prateek Bhakta, office hours Mondays 2-4 outside theory offices, pbhakta@gatech.edu
My (tentative) office hours: Tu, Th 1:30-2:30, Klaus 2041, randall@cc.gatech.edu

Course Outline

Useful references:

• Chapters 12 and 13 of Mertens and Moore.
• 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: (Caveat emptor! Most of the lecture notes included have not been carefully proofread or edited.)

• Fundamentals of counting and random walks
  
  • August 19, 21: Exact counting: Kasteleyn's mathod for counting perfect matchings and the Matrix Tree Theorem for counting spanning trees
  • August 26: Counting matchings (domino tilings) on lattice graphs.
    • The Gessel Viennot method for counting noninteresecting lattice paths
    • Domino shuffling and tilings of the Aztec Diamond
  • August 28: Equivalence between approximate counting and sampling PDF (EV) and PDF (DR) (for approx counting -> sampling)
  • September 2, 4: Markov chain fundamentals PDF (EV)
  • September 9: Spectral gaps
  • September 11: Measuring convergence rate for walks on the hypercube and the Riffle shuffle
  
  
• Coupling
  
  • September 16: Coupling: Mark Jerrum's book and some lecture notes 1 (EV)
  • September 18: Sampling k-colorings and
  • September 23: Coupling from the past
  • September 25, 30: Sampling lattice configuations: tilings and 3-colorings. The original paper and Notes: Part 1, Part 2 Part 3
  
  
• Flows and Conductance
  
  • October 2, 7: Conductance, congestion and canonical flows (Jerrum's book -- Chapter 5)
  • October 9: Sampling matchings and perfect matchings in dense graphs
  • October 14: Estimating the partition function for matchings and approximately counting k-colorings
  • October 16, 21: Estimating the permanent (and sampling matchings in any bipartite graph)
  • October 23, 28: Ising
  
  
• Auxilliary methods and applications
  • October 30: Intro to the Comparison and Decomposition Methods
  • November 6, 11: Lectures by Santosh Vempala: Estimating the volume of a convex body (Vempala's survey)
  • November 13: The Comparison and Decomposition Theorems (Also see this for nice proofs)
  
  
• Student presentations
  • November 18
    • Exponential Metrics
    • Stopping Times
  • November 20 - No class. Instead meet outside of Klaus 2140 to discuss Homework 3 (optional)
  • November 25
    • Complexity of the permanent and sampling independent sets
    • Simulated tempering and swapping (and the slides)
  • December 2
    • Sampling independent sets up to the tree threshold
    • Sampling mixtures of Gaussians
  • December 4
    • Testable algorithms for self-avoiding walks

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 30 minute summary to the class the last few weeks of classes. You can work along or in groups of 2.

Student presentations:
• November 18:
  • EC and SC: Sampling from distributions with Expential Metrics
  • BC and AR: Lovasz and Winkler: Stopping rules to bound mixing rates
    
• November 20: No class today! SCS Distinguished Lecture by Deborah Estrin 11:00 - 12:00, with reception to follow (fyi).
• November 25:
  • DM and RK Valiant: The Permanent is #P-Complete and Dyer, Frieze, Jerrum: Counting independent sets in sparse graphs
    
  • JT and JS: Bhatnagar, Randall: Slow mixing of simulated tempering on the Potts model
    
• December 2:
  • RB and RT: Dyer, Sinclair, Vigoda, Weitz: Mixing in time and space
    
  • TS and MF: Lower Bounds for the Gibbs Sampler over Mixtures of Gaussians
• December 4:
  • JF and LC, Dec 4: Randall, Sinclair: Testable algorithms for sampling self-avoiding walks
    

Homework 2 Due October 21

Homework 3 Due December 2
Here is a summary of the two decomposition theorems. Please feel free to deviate from the outline in the second question if you decide to use the "state decomposition theorem" based on a decomposition of the state space into overlapping sets (instead of the partition version that is outlined in the question).

Mini-assignment for those who got under 30 on hw 1:

• Redo number 3 from the last homework. Please analyze the chain we did in class, not the one in MJ's book!
• Try to analyze the tower chain for lozenge tilings using path coupling.
• Read the solutions to see what is expected.
• Please let me know that you did these things! Thanks.

Homework 2 Due March 31

Homework 3 Due April 21. You do not have to hand this one in.