Sharp Thresholds for Mixing Times

December 20 to December 23, 2004

at the

American Institute of Mathematics, Palo Alto, California

organized by

Amir Dembo, Yuval Peres, and David Revelle

This workshop, sponsored by AIM and the NSF, 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.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and working sessions.

Invited participants include D. Aldous, L. Babai, G. Ben Arous, F. Chung, R. D'Souza, A. Dembo, P. Diaconis, J. Fill, A. Gamburd, N. Gantert, S. Goel, S. Goldwasser, T. Hayes, A. Karlin, G. Kordzakhia, M. Mihail, B. Morris, E. Mossel, A. Nachmias, Y. Peres, A. Puha, P. Ralph, D. Randall, D. Revelle, L. Saloff Coste, C. Schoolfield, D. Shah, S. Sheffield, A. Sinclair, P. Tetali, V. Vu, E. Wilmer, D. Wilson, P. Winkler, and D. Zhan.

The deadline to apply for support to participate in this workshop has passed.

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Return to the AIM Research Conference Center.