Sharp Thresholds for Mixing Times

December 20 to December 23, 2004

at the

American Institute of Mathematics, San Jose, California

organized by

Amir Dembo, Yuval Peres, and David Revelle

Original Announcement

This workshop will address basic questions about the mixing times of Markov chains. The mixing times of Markov chains are fundamental parameters that encode key geometric information about the chain and at the same time have a wide variety of applications. Markov chain Monte Carlo methods were first used by physicists as a means for simulating Gibbs measures. In the last twenty years, computer scientists and probabilists have brought new perspectives and methods to this study. They have also applied it to other areas, such as approximately uniform sampling and approximate counting of complex combinatorial structures, and to the computation of high-dimensional volumes and integrals.

We intend for the workshop to try and make progress on one of the fundamental open questions about mixing times of Markov chains:

When is there a sharp threshold for the total variation mixing time?

For some Markov chains, such as random walk on the hypercube, there is a sharp threshold for the mixing time, whereas for random walks on other graphs, such as a torus, there is no such sharp threshold. We expect that the workshop will investigate whether that there is a sharp threshold if the relaxation time is of a lower order of magnitude than the mixing time. This is analogous to a criterion of Aldous for concentration of the cover time. Another goal would be to obtain direct geometric criteria for a sharp threshold in important families of Markov chains, such as random walks on the permutation group S_n (shuffling models) and Glauber dynamics for the Ising model and for proper coloring on a finite graph of n vertices. A related question for these two families is to characterize when the mixing time is of order n log(n).

Because these questions have applications in such a wide variety of fields, a rich variety of techniques have been developed to study mixing times, including: probabilistic methods involving martingales, large deviations, and coupling; analytic methods involving spectral gap estimates, log-Sobolev inequalities and hypercontractivity; combinatorial methods involving canonical paths, flows and optimal cutsets; and geometric ideas relating isoperimetric inequalities to eigenvalues of the Laplacian. By bringing together experts on a variety of these different techniques, we hope that perhaps some of them can be combined or modified to obtain the necessary insights into the problems.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.