Glauber dynamics on trees: Boundary conditions and mixing time
Markov Chains in Algorithms and Statistical Physics
February 01, 2005 11:00 AM to 11:30 AM
Speakers:
|
 |
Abstract: |
The Glauber dynamics (a local MCMC algorithm for spin systems) is
known to work very well (i.e., get close to equilibrium in n\log n
steps) when the interaction between neighboring sites is weak
enough. When the interaction is strong, there are settings in which
the dynamics is slowly mixing (mixing time superpolynomial in the
number of sites). In particular, a strong interaction may lead to a
stationary distribution which is bi-modal, i.e., the distribution is a
non-trivial combination of two well-separated distributions (or
phases), in which case the dynamics is slow due to the bottleneck at
the border between the two phases. However, it is conjectured that the
dynamics mixes rapidly (in polynomial time) inside each phase. In
other words, if the stationary distribution is limited to one of the
phases by introducing an appropriate boundary condition then it is
believed that there are no more bottlenecks. Formalizing this
intuition, however, remained elusive for the last decade.
The main source of difficulty is that existing arguments for
establishing rapid mixing are not sensitive to the boundary condition,
and thus cannot be used in situations such as the above, where the
mixing time depends heavily on the boundary. In this work we give the
first rapid mixing results which are boundary specific by considering
systems on trees. In particular, we show that the mixing time of the
Glauber dynamics for the Ising model on an n-vertex regular tree with
plus-boundary remains O(n\log n) at all temperatures (in contrast to
the free boundary case, where the mixing time is not bounded by any
fixed polynomial at low temperatures). At the core of our argument is
the ability to deduce rapid mixing of the dynamics from decay of
correlations in the stationary distribution, for a specific boundary
condition. In addition, we show that the needed decay of correlations
can be verified by a simple calculation, thus yielding a very simple
criterion for O(n\log n) mixing time. We apply this criterion to
various models, including the Ising model, Colorings, Independent Sets
and the Potts model, and substantially extend the range of parameters
for which rapid mixing is known to hold in these models.
Joint work with Fabio Martinelli and Alistair Sinclair. |
|
|
