Gibbs rapidly samples colorings of G(n, d/n)

• 成果类型: Article
• 署名作者: Mossel, Elchanan; Sly, Allan
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-009-0222-x
• 发表日期: 2010
• 页码: 37-69
• 关键词: algorithm

摘要

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 Erdos-Renyi random graph G(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n, d/n) is d(1-o(1)), it contains many nodes of degree of order (log n)/(log log n). The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n, d/n) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature beta, the mixing time of Gibbs sampling is at least n(1+Omega(1/log log n)) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work we consider sampling q-colorings and show that for every d < infinity there exists q(d) < infinity such that for all q >= q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does not depend on n. 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 npolylog(n). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the Weitz tree, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erdos-Renyi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They 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 there exists an alpha > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Gamma of length O(log n) satisfies Sigma(u)is an element of Gamma Sigma(v not equal u) alpha(d(u, v)) = O(log n). The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.