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.
Previous attempts at studying this problem for sampling uniform colorings yielded weaker results. @cite_9 it is shown that Gibbs sampling rapidly mixes on @math if @math where @math and that a variant of the algorithm rapidly mixes if @math . Indeed the main open problem of @cite_9 is to determine if one can take @math to be a function of @math only.
@cite_9
2048759201
We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ λ c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.