Markov Chain Monte Carlo and Applications, Spring 2008

Instructor :  Nayantara Bhatnagar (email: nayan @ stat.berkeley.edu)
Lectures :  MW 1.30-3 pm, 340 Evans Hall.
Office Hours :  Tuesday 10 am - 11 am, Friday 10 am -11 am in Room 325, Evans Hall.
Text : There is no required text, but you may consult the following books as well the several sets of lecture notes from previous courses, listed below.
1) Mark Jerrum's monograph Counting, Sampling and Integrating (available online here in the form of lecture notes)
2) Alistair Sinclair's monograph Algorithms for Random Generation and Counting
3) Robert and Casella's Monte Carlo Statistical Methods

Lecture notes from other courses:
Dana Randall's course notes on Mixing Rates of Markov Chains
Eric Vigoda's course notes on MCMC Methods
Ravi Montenegro's course notes on Convergence of Markov Chains
Alistair Sinclair's course notes on MCMC: Foundations and Applications

Prerequisites: Some familiarity with analysis of algorithms and non-measure-theoretic probability is desirable.

Requirements for the course include
1) Scribing one or more lecture notes. (template)
2) Choosing a project, preparing a 4-5 page writeup and a half-hour (slide) presentation.
3) Turning in exercises.
[HW1] -  due February 20.

Rough plan of lectures:
Fundamentals and combinatorial applications:
Jan 23: Introduction to MCMC.  [AS1], [AS2].
Jan 28: Fundamental theorem, mixing time and its characterization by spectral gap. [pdf]
Jan 30: Eigenvalues and Expansion, Conductance characterizes the mixing time of reversible chains. [pdf]
Feb 4: Comparison of Markov chains, Canonical Paths theorem [RM8], [RM9]
Feb 6: Fabio Martinelli will lecture on "The East Model: A Case Study from Statistical Physics."
Feb 11: Multicommodity flow [AS12]
Feb 13, 20: Sampling matchings  [AS13]. Estimating coefficients of the matching polynomial using log-concavity [AS14].
Feb 25 Equivalence of approximate counting and sampling [EV4], [MJ3]. Polynomial approximation implies FPRAS [AS16]
Feb 27 Estimating the Permanent of a Non-negative Matrix. [JSV01]  (See [BSVV06] and [SVV06] for work on faster annealing.)
Mar 3 Coupling (basics, another proof of the fundamental theorem, sampling colorings) [EV6]
Mar 5: Coupling from the past [EV7]
Mar 10: Path coupling, Jerrum's Coupling [EV8]
Mar 12,17: Glauber dynamics for coloring (Coupling using properties of random colorings) [FV07]
Mar 19: Convergence Diagnostics, Stopping Times
Spring Break
Mar 31: Alexandre Stauffer spoke on an Importance Sampler for Generating Binary Contingency Tables [JB07]
Applications from Statistical Physics (with some unrelated topics interspersed):
Apr 7: A simple condition on spectral radius for rapid mixing of Glauber dynamics [TH06]
Apr 9: Approximately counting knapsack solutions by dynamic programming [MD03]
Apr 14: Decay of corellations on computation trees impies FPTAS and rapid mixing of dynamics (independent sets) [DW06]
Apr 16: Joel Mefford will talk about Langevin diffusions and MCMC algorithms.
Apr 21: Peirls arguments for showing slow mixing of Ising model on Z^2 [DR06]
Apr 23: Partha Dey will speak on the connection between spatial and temporal mixing on lattices. [DSVW02]
Applications from Statistics:
Apr 28,30: Volume computation
May 5 Maximum Likelihood Methods, phylogeny
May 7: Temperature based methods (annealling and simulated tempering)
May 12: TBD