TY - JOUR

T1 - Exact thresholds for ising-gibbs samplers on general graphs

AU - Mossel, Elchanan

AU - Sly, Allan

PY - 2013/1

Y1 - 2013/1

N2 - 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 Cnlog 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 n1+Θ(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.

AB - 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 Cnlog 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 n1+Θ(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.

KW - Glauber dynamics

KW - Ising model

KW - Phase transition

UR - http://www.scopus.com/inward/record.url?scp=84875003099&partnerID=8YFLogxK

U2 - 10.1214/11-AOP737

DO - 10.1214/11-AOP737

M3 - Article

SN - 0091-1798

VL - 41

SP - 294

EP - 328

JO - Annals of Probability

JF - Annals of Probability

IS - 1

ER -