Sharp Thresholds for Mixing Times
December 20 to December 23, 2004
American Institute of Mathematics,
Palo Alto, California
and David Revelle
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:
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.
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 Sn (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).
- When is there a sharp threshold for the
total variation mixing time?
Because these questions have applications in such a wide variety
a rich variety of techniques have been developed to study mixing times,
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.
A list of open problems.