Instructor: Alistair Sinclair
Meets: TuTh 9:30-11:00 in 310 SodaShort Description: The Markov chain Monte Carlo method (MCMC) is by now well established as a powerful algorithmic paradigm, with applications in areas such as statistical physics, approximate counting, computing volumes and integrals, and combinatorial optimization. Typically it is used without rigorous justification, so that numerical results derived from it have to be taken on faith. More recently, theoretical computer scientists and mathematicians have developed new techniques for analyzing MCMC algorithms, which allow one to derive precise performance guarantees for them. The techniques fall into three main domains - probabilistic, combinatorial and geometric - and are of interest in their own right, having connections to such topics as expander graphs, isoperimetric inequalities and multicommodity flow. This course will introduce these techniques and use them to obtain provably efficient MCMC algorithms for a variety of problems. It will also touch on some related topics, such as phase transitions in statistical physics, simulated annealing and genetic algorithms, and the complexity of combinatorial enumeration problems.
Tentative Syllabus (as time permits):
- Basis of the Markov chain Monte Carlo (MCMC) method: ergodicity,
stationary distributions, reversibility, mixing times.
- Some applications of random sampling: card shuffling, approximate
counting, volume and integration, statistical physics, combinatorial
optimization.
- Mixing times I: probabilistic methods. Stopping times, coupling,
path coupling, Dobrushin uniqueness, perfect sampling (coupling
from the past and Fill's algorithm). Applications: simple shuffles,
planar lattice structures, independent sets and colorings, etc.
- Mixing times II: multicommodity flow. Reversible Markov chains
and eigenvalues, canonical paths and flows, Diaconis-Stroock
comparison technique. Applications: monomer-dimer model and
matchings, the Ising model, 0-1 knapsack problem, etc.
- Mixing times III: geometry. Conductance and isoperimetric inequalities,
expanders, the Cheeger bound, "average" conductance. Applications:
volume, contingency tables, "torpid" mixing of Glauber dynamics
("critical slowing down").
- Phase transitions in statistical physics and their relationship
to MCMC.
- Approximate counting: #P-completeness, fully-polynomial approximation
schemes, robustness of approximation for counting problems.
- Search heuristics in combinatorial optimization. The Metropolis
algorithm, simulated annealing, simulated tempering etc.
- Non-linear stochastic processes. Quadratic dynamical systems,
population genetics, genetic algorithms.