Title: Glauber dynamics on trees: Boundary conditions and mixing time
Speaker: Dror Weitz, Institute for Advanced Study
Date: November 8, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, CoRE 301, Room A, Rutgers University, Busch Campus, Piscataway, NJ
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