Title:
Glauber dynamics on trees: Boundary conditions and mixing time

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. A main source of difficulty is that most of the existing 
arguments for establishing rapid mixing are local in nature and immediately 
imply rapid mixing for all boundary conditions and are thus not sensitive
enough for the above setting, where the mixing time is known to be slow
for some boundary conditions.

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.  A crucial novel 
property of our implication is that the assumption of decay of correlations 
needs only hold for the specific boundary condition under consideration 
rather than for all boundary conditions.  In addition, we show that the 
needed decay of correlations can be verified by a simple calculation and 
this gives a very simple criterion for O(n\log n) mixing time of the 
Glauber dynamics for systems on trees.  We apply this criterion to 
various models and substantially extend the range of parameters for which 
rapid mixing is known to hold in these models, which include the Ising 
model, Colorings, Independent Sets and  the Potts model.

Joint work with Fabio Martinelly and Alistair Sinclair