期刊
ANNALS OF PROBABILITY
卷 41, 期 1, 页码 294-328出版社
INST MATHEMATICAL STATISTICS
DOI: 10.1214/11-AOP737
关键词
Ising model; Glauber dynamics; phase transition
资金
- Alfred Sloan fellowship in Mathematics
- NSF CAREER Grant [DMS-05-48249]
- DOD ONR Grant [N0014-07-1-05-06]
- BSF Grant [2004105]
- ISF Grant [1300/08]
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 beta < 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 beta, 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 beta < 1, with high probability over the Erdos-Renyi random graph G(n, d/n), it holds that the mixing time of Gibbs samplers is n(1+Theta(1/loglog n)). Both results are tight, as it is known that the mixing time for random regular and Erdos-Renyi random graphs is, with high probability, exponential in n when (d - 1) tanh, beta > 1, and d tanh beta > 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据