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---

Important