Exact thresholds for Ising-Gibbs samplers on general graphs

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 $\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+Θ({1}/{\log\log 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.

Published in at http://dx.doi.org/10.1214/11-AOP737 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Ising models on locally tree-like graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Coupling with the stationary distribution and improved sampling for colorings and independent sets

Cited by in corpus (13)

• Quantum speedup of Monte Carlo methods
• Spatial mixing and approximation algorithms for graphs with bounded connective constant
• The Ising Partition Function: Zeros and Deterministic Approximation
• Metastability of the Ising model on random regular graphs at zero temperature
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Efficiency Optimization in Quantum Computing: Balancing Thermodynamics and Computational Performance
• The worm process for the Ising model is rapidly mixing
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Stochastic dynamics and the Polchinski equation: an introduction
• Kawasaki dynamics beyond the uniqueness threshold
• Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
• Equi-Energy sampling does not converge rapidly on the mean-field Potts model with three colors close to the critical temperature
• Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs