Mathematics – Probability
Scientific paper
2009-03-17
Mathematics
Probability
29 pages
Scientific paper
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 {\em any} graph of $n$ vertices and maximal degree $d$, where all interactions are bounded by $\beta$ and arbitrary external fields is bounded by $C n \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 the when $d \tanh \beta < 1$, with high probability over the Erd\H{o}s-R\'enyi random graph $G(n,d/n)$, it holds that the mixing time of Gibbs Samplers is $n^{1+\Theta(\frac{1}{\log \log n})}$. Both results are tight as it is known that the mixing time for random regular and Erd\H{o}s-R\'enyi 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.
Mossel Elchanan
Sly Allan
No associations
LandOfFree
Exact Thresholds for Ising-Gibbs Samplers on General Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exact Thresholds for Ising-Gibbs Samplers on General Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Thresholds for Ising-Gibbs Samplers on General Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-491098