Exact thresholds for Ising–Gibbs samplers on general graphs
Date
2013
Authors
Mossel, Elchanan
Sly, Allan
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Mathematical Statistics
Abstract
We establish tight results for rapid mixing of Gibbs samplers for the Ferromagnetic
Ising model on general graphs. We show that if
(d − 1)tanhβ < 1, then there exists a constant C such that the discrete time mixing time of Gibbs
samplers for the ferromagnetic Ising model on any graph of n vertices and
maximal degree d, where all interactions are bounded by β, and arbitrary external
fields are bounded by Cn log n. Moreover, the spectral gap is uniformly
bounded away from 0 for all such graphs, as well as for infinite graphs of
maximal degree d. We further show that when d tanhβ < 1, with high probability over the
Erdos–Rényi random graph G(n, d/n), it holds that the mixing time of Gibbs
samplers is n¹⁺ᶱ(1/log log n). Both results are tight, as it is known that the mixing time for random regular
and Erdos–Rényi random graphs is, with high probability, exponential ˝
in n when (d − 1)tanhβ > 1, and d tanhβ > 1, respectively. To our knowledge
our results give the first tight sufficient conditions for rapid mixing of
spin systems on general graphs. Moreover, our results are the first rigorous
results establishing exact thresholds for dynamics on random graphs in terms
of spatial thresholds on trees.
Description
Keywords
Keywords: Glauber dynamics; Ising model; Phase transition
Citation
Collections
Source
The Annals of Probability
Type
Journal article
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description