Markov

Mathematics of Markov Chain Monte Carlo


Co-sponsored by Mathematical Sciences Research Institute

REGISTRATION FOR THIS WORKSHOP IS NOW CLOSED

How many times should a deck of cards be shuffled before the order of the cards is close to random? If a random walker moves among linked sites in a network by choosing, at each move, randomly among the sites connected by a single link to her current position, how long before her location is (almost) uniformly distributed in the network?

Both scenarios are examples of ergodic Markov chains, a class of random processes which over time settle down into an equilibrium distribution. The mixing time of a Markov chain quantifies how long the chain must be run before its distribution is close to this equilibrium. Obtaining bounds on mixing times is of great practical interest when using Markov chains to simulate, a technique known as Markov chain Monte Carlo. Furthermore, the rigorous analysis of mixing time behavior is a rich mathematical field using probabilistic, analytic, and geometric tools, with connections to phase-transition phenomena in statistical physics.

In the past two decades, a wide range of techniques have been developed for obtaining rigorous bounds on mixing times. Many of these ideas, as well as concrete examples from combinatorics and statistical physics can be included in undergraduate courses. The workshop is aimed at instructors interested in expanding the undergraduate probability curriculum to include developments on mixing times, or who wish to learn about this still growing field.

Topics will include basics of finite Markov chains, coupling, strong stationary times, cover and hitting times, and a discussion of the Ising model. In addition, there will be a computer lab, where some of the theoretical results can be explored through simulation. The required background is an undergraduate course in probability. A manuscript suitable for a course, written by the organizers, will be made available to the participants prior to the workshop. For more information, please visit the workshop webpage at http://www.oberlin.edu/markov/