An MAA PREP workshop for faculty teaching undergraduate probability, graduate students, and/or advanced undergraduate students.

An MAA PREP activity funded by NSF (grant DUE-0341481). Also partly supported by MSRI, NSF grant #0244479, and an NSF VIGRE grant to the Department of Statistics, University of California, Berkeley.

Workshop

Home

Schedule
(w/links)

Speakers and organizers

References

Book

Main page

Questions?

Please write!

The workshop

Mathematics of Markov Chain Monte Carlo was held from Monday, June 12 through Friday, June 16 at the Mathematical Sciences Research Institute in Berkeley, California.

Topics included:

• Basics of finite Markov chains. Definitions, convergence theorem.
• Coupling. Mixing times for random walk on torus and hypercube.
• Strong stationary times and shuffling.
• Path coupling. Fast mixing for colorings.
• Cover and hitting times.
• The Ising model.
  • Introduction and basic properties.
  • Fast convergence at high temperature.
  • Slow convergence at low temperature. Metastability.
• Coupling from the past.

Click for a detailed schedule, including links to videos of the talks and speaker slides.

Organizers and course instructors

• David A. Levin, Department of Mathematics, University of Oregon.
• Yuval Peres, Departments of Mathematics and Statistics, University of California, Berkeley.
• Elizabeth L. Wilmer, Department of Mathematics, Oberlin College.

Guest speakers

• Raissa D'Souza, College of Engineering, University of California, Davis.
• Thomas Hayes, Department of Computer Science, University of California, Berkeley.
• Alistair Sinclair, Department of Computer Science, University of California, Berkeley.

Click for more information on the organizers and speakers and suggestions for further reading.

Overview

Markov chains are a class of stochastic processes which (under mild regularity conditions) converge to a unique stationary distribution. Traditional undergraduate treatments of Markov chains examine fixed chains as time goes to infinity. In the past two decades, a different asymptotic analysis has emerged. For a Markov chain with a large state space, we care about the finite number of steps needed to get the distribution reasonably close to its limit. This number is known as the mixing time of the chain. There are now many methods for determining its behavior as a function of the geometry and size of the state space.

In 1986, Aldous and Diaconis wrote a wonderful Monthly article on mixing times. Since then, both the field and its interactions with computer science and statistical physics have grown tremendously. In the spring of 2005, mixing times of finite Markov chains were a major theme of the multidisciplinary research program Probability, Algorithms, and Statistical Physics, held at MSRI.

Many of these exciting developments can and should be communicated to undergraduates. We are writing a textbook, Markov Chains and Simulation, on this beautiful, relevant, and accessible material. It is intended for a second undergraduate course in probability and emphasizes current developments in the rigorous analysis of convergence time for Markov chains. This workshop will present a detailed outline for a course based on this text.

This course will expose students to both key mathematical concepts and the interactions of mathematics with other disciplines. The models which we will analyze in the workshop will largely be "particle systems" arising in statistical physics. Interestingly, many of these models exhibit phase transitions: the behavior of the model may change abruptly as a parameter describing local interactions passes through a critical value. For our particle systems, the mixing time may vary from "fast" (polynomial in the instance size n) to "slow" (exponential in n) as interaction parameters pass through a critical value.

back to the main book page

(Thanks to David Wilson for pictures 2 and 4 above)