Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd o s-R 'enyi random graph G(n,d n). While the average degree in G(n,d n) is d(1-o(1)), it contains many nodes of degree of order @math . The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring or the Ising model, the mixing time of Gibbs sampling is at least @math . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. In this work consider sampling q-colorings and show that for every $d 1 where the number of colors does not depend on n. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.
@cite_20: In this work we show that for every @math , such that for all @math where the parameters of the model do not depend on @math . They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than @math . Our proof exploits in novel ways the local treelike structure of Erd o s-R 'enyi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex @math of the graph has a neighborhood @math of radius @math in which the induced sub-graph is a tree union at most @math edges and where for each simple path in @math the sum of the vertex degrees along the path is @math . Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for @math it applies for all external fields and @math , where @math is the critical point for decay of correlation for the Ising model on @math .
@cite_8: Consider the problem of approximately counting weighted independent sets of a graph G with activity λ, i.e., where the weight of an independent set I is λ|I|. We present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree Δ and λ< λc=(Δ-1)Δ-1 (Δ-2)Δ. This improves on the previously known general bound of λ ≤ (2 ‾ Δ-2). The new regime includes the interesting case of λ=1 (uniform weights) and Δ ≤ 5. The previous bound required Δ ≤ 4 for uniform approximate counting and there is evidence that for Δ ≥ 6 the problem is hard. Note that λc is the critical activity for uniqueness of the Gibbs measure on the regular tree of degree Δ, i.e., for λ ≤ λc the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. Indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. We show that on any graph of maximum degree Δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. This resolves an open conjecture in statistical physics. Our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. Also, by existing arguments, establishing decay of correlations for all graphs and λ<λc gives that the Glauber dynamics is rapidly mixing in this regime. However, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the Glauber dynamics is limited to this class of graphs.
Comparing the results presented here to @cite_20 we observe first that there is one sense in which the current results are weaker. @cite_20 the tree access @math can be of order @math while for the results presented here @math has to be of order @math . The results of @cite_20 crucially use the fact that the Ising model is attractive (this is a monotonicity property) and that it is a two spin system which allows using the Weitz tree'' @cite_8 .