Logo

Mathematical Sciences Research Institute

Home » Mathematics of Markov Chain Monte Carlo

Workshop

Mathematics of Markov Chain Monte Carlo June 12, 2006 - June 16, 2006
Organizers David A. Levin, Yuval Peres, Elizabeth Wilmer
Speaker(s) No Speakers Assigned Yet.
Description 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 ric 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 detailed information, go to the workshop website. This is a Professional Enhancement Program of the Mathematical Association of America. To participate, you must apply by May 2, 2006 at the MAA website. Go to http://www.maa.org/prep/2006/ and use the registration buttons on the left side of this page. SCHEDULE MONDAY, JUNE 12 8:30-8:50 Registration 8:50-9:00 Welcome --Hugo Rossi, MSRI Deputy director 9:00-9:45 Overview and introduction to simulation --Yuval Peres Permutations, proper colorings on a line and a tree 9:45-10:15 Coffee Break and particpant introductions A-K 10:15-11:00 Basics of Markov chains -- Elizabeth Wilmer 2 by 2 chains, irreducibility, aperiodicity, stationary distribution construction via stopping time, example: simple RW on graph 11:15-12:00 Interactive session: Counting and simulation Hardcore configurations on the line and on a tree. Parity of permutations, the 15 puzzle. One round of cyclic-to-random transpositions is not uniform. 12:00-2:00 LUNCH 2:00-2:45 Basics of mixing -- David Levin: Total-variation distance, submultiplicativity, the convergence theorem, uniqueness of stationary measure as a consequence, reversible chains 2:45-3:15 Coffee Break and Participant introductions L-Z 3:15-4:00 Interactive session Irreducibility example (3 colorings of tree) Coupon collector problem 4:00 Discussion TUESDAY, JUNE 13 9:00-9:45 Interactive session: Hitting and cover times on the cycle. 9:45-10:15 Break 10:15-11:00 Coupling -- David Levin The general bound, the hypercube and the cycle 11:15-12:00 Strong stationary times and shuffling -- Elizabeth Wilmer top-to-random insertion, the hypercube 12:00-2:00 LUNCH 2:00-2:45 A first look at lower bounds: Yuval Peres top-to-random insertion The bottleneck ratio 2:45-3:15 Break 3:15-4:00 Interactive session: coupling and strong uniform times coupling on the torus, coordinatewise; coupling on complete graph, and two glued complete graphs; strong uniform times for same example. The half-diameter lower bound on t_mix(1/2) 4:00 Discussion WEDNESDAY, JUNE 14 9:00-9:45 The Kantorovich metric and path coupling --Yuval Peres 9:45-10:00 Break 10:00-11:00 An overview of applications in Computer Science --Alistair Sinclair 11:15-12:15 Lower bounds- Tom Hayes Lower bound on cycle and torus via variance, hypercube via Chebyshev; Proper colorings of complete graph General lower bound for Glauber dynamics (statement) 12:15- LUNCH ---FREE AFTERNOON--- THURSDAY, JUNE 15 9:00-9:45 Simulating Glauber dynamics for the ising model: Raissa D'Souza 9:45-10:15 break 10:15-11:00 The Ising model on the complete graph -- Yuval Peres 11:15-12:00 Interactive session: More lower bounds Random transpositions, Random adjacent transpositions, east model *Advanced Homework: Durrett Reversal chain 12:00-2:00 LUNCH 2:00-2:45 Phase transitions in simulation and theory: Raissa D'Souza 3:15-4:00 Interactive session: Waiting times for patterns in coin-tossing 4:00 Discussion and Participant comments FRIDAY, JUNE 16 9:00-9:45 Cover times and lamplighter groups -- Elizabeth WIlmer Matthews bound, Uniformity of cover point on cycle. 9:45-10:15 BREAK and Participant comments 10:15-11:00 Interactive session: Glauber dynamics for Ising model on the cycle 11:15-12:00 Perfect sampling and coupling from the past -- Yuval Peres 12:00 Workshop conclusion ---FREE AFTERNOON---

Schedule
Show All Collapse
Jun 13, 2006
10:15 AM - 11:00 AM
  Coupling
David Levin
11:15 AM - 12:00 PM
  Strong stationary times and shuffling
Elizabeth Wilmer
02:00 PM - 02:45 PM
  A first look at lower bounds: the top-to-random shuffle and the bottleneck ratio
Yuval Peres
Jun 14, 2006
09:00 AM - 09:45 AM
  The Kantorovich metric and path coupling
Yuval Peres
10:15 AM - 11:00 AM
  An overview of applications in computer science
Alistair Sinclair
11:15 AM - 12:15 PM
  More lower bounds: the cycle, the torus, the hypercube,More lower bounds: the cycle, the torus, the hypercube,More lower bounds: the cycle, the torus, the hypercube, and general bounds for Glauber dynamics
Thomas Hayes
Jun 15, 2006
09:00 AM - 09:45 AM
  Simulating Glauber dynamics for the Ising model
Raissa D'Souza
10:15 AM - 11:00 AM
  The Ising model on the complete graph
Yuval Peres
02:00 PM - 02:45 PM
  Phase transitions in simulation and theory
Raissa D'Souza
Jun 16, 2006
09:00 AM - 09:45 AM
  Cover times and lamplighter groups
Elizabeth Wilmer
11:15 AM - 12:00 PM
  Perfect sampling and coupling from the past
Yuval Peres