Mathematics of Markov Chain Monte CarloDavid
A. Levin, Yuval Peres, Elizabeth Wilmer
June 12-16, 2006
Mathematical Sciences Research
Institute
Berkeley, CA
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/