Abstract
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ős–Rényi 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 β, the mixing time of Gibbs sampling is at least n 1+Ω(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 < ∞ there exists q(d) < ∞ 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 Erdős–Rényi 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 α > 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 Γ of length O(log n) satisfies \({\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}\) . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs. (Book in preparation.) Current version online at http://stat-www.berkeley.edu/users/aldous/book.html
Berger N., Kenyon C., Mossel E., Peres Y.: Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields 131(3), 311–340 (2005)
Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 223–231 (1997)
Chen, M.F.: Trilogy of couplings and general formulas for lower bound of spectral gap. In: Probability towards 2000, number 128 in Lecture Notes in Statistics (1998)
Dyer M., Flaxman A.D., Frieze A.M., Vigoda E.: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms 29(4), 450–465 (2006)
Dyer, M., Frieze, A., Hayes, T., Vigoda, E.: Randomly coloring constant degree graphs. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), pp. 582–589 (2004)
Dyer, M., Frieze, A., Jerrum, M.: On counting independent sets in sparse graphs. In: Proceedings of 40th IEEE Sypmosium on Foundations of Computer Science (FOCS), pp. 210–217 (1999)
Dyer M.E., Greenhill C.S.: On Markov chains for independent sets. J. Algorithms 35(1), 17–49 (2000)
Efthymiou, C., Spirakis, P.G.: Randomly colouring sparse graphs using a constant number of colours (2007, unpublished)
Frieze A.M., McDiarmid C.: Algorithmic theory of random graphs. Random Struct. Algorithms 10(1-2), 5–42 (1997)
Gershchenfeld, A., Montanari, A.: Reconstruction for models on random graphs. In: Foundations of Computer Science, Annual IEEE Symposium, pp. 194–204. IEEE Computer Society (2007)
Goldberg, L.A., Martin, R., Paterson, M.: Strong spatial mixing for lattice graphs with fewer colours. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), pp. 562–571 (2004)
Hayes, T.P.: A simple condition implying rapid mixing of single-site dynamics on spin systems. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 39–46 (2006)
Jerrum M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms 7, 157–166 (1995)
Jerrum M., Sinclair A.: Approximating the permanent. SIAM J. Comput. 18(6), 1149–1178 (1989)
Jerrum M., Sinclair A., Vigoda E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51(4), 671–697 (2004)
Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. In: 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 568–578. IEEE Computer Soc., Los Alamitos, CA (2001)
Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on Probability Theory and Statistics (Saint-Flour, 1997), vol. 1717 of Lecture Notes in Mathematics, pp. 93–191. Springer, Berlin (1999)
Martinelli, F., Sinclair, A., Weitz, D.: The ising model on trees: boundary conditions and mixing time. In: Proceedings of the Forty Fourth Annual Symposium on Foundations of Computer Science, pp. 628–639 (2003)
Mossel, E., Sly, A.: Rapid mixing of gibbs sampling on graphs that are sparse on average. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 238–247 (2008)
Mossel, E., Sly, A.: Rapid mixing of gibbs sampling on graphs that are sparse on average. Random Struct. Algorithms (2009, to appear)
Mossel E., Weitz D., Wormald N.: On the hardness of sampling independent sets beyond the tree threshold. Prob. Theory Relat. Fields 143, 401–439 (2009)
Shamir E., Upfal E.: Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces. J. Algorithms 5(4), 488–501 (1984)
Vigoda E.: A note on the glauber dynamics for sampling independent sets. Electron. J. Comb. 8(1), 1–8 (2001)
Weitz, D.: Counting indpendent sets up to the tree threshold. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 140–149. ACM (2006)
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
E. Mossel supported by an Alfred Sloan fellowship in Mathematics and by NSF grants DMS-0528488, DMS-0548249 (CAREER) by DOD ONR grant N0014-07-1-05-06 and A. Sly supported by NSF grants DMS-0528488 and DMS-0548249.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Mossel, E., Sly, A. Gibbs rapidly samples colorings of G(n, d/n). Probab. Theory Relat. Fields 148, 37–69 (2010). https://doi.org/10.1007/s00440-009-0222-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-009-0222-x