×

Exact thresholds for Ising-Gibbs samplers on general graphs. (English) Zbl 1270.60113

Gibbs sampling is a standard model for the temporal evolution of spin systems and a technique for sampling high-dimensional distributions. The study of convergence rate of Gibbs samplers, typically studied on lattices, for computer science purposes and spin-glasses theory, has been extended to general graphs of bounded degrees.
In the present paper, the Gibbs sampling is considered for the ferromagnetic Ising model on general graphs. Criteria are provided for a rapid convergence of the pertinent dynamics, for any graph and any external field. Specifically, the rapid mixing is quantified and tight sufficient conditions for mixing to occur in spin systems, are given. Lower bounds are established on the spectral gap of the continuous time Glauber dynamics which are independent of the size of the graph. The proofs are short, however, it is worth to mention that the authors’ method is fundamentally different from previous approaches in this area. The main novelty is a new application of the censoring technique, developed for the study of Markov chains.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Aldous, D. and Fill, J. A. Reversible Markov chains and random walks on graphs. Unpublished manuscript. Available at .
[2] Berger, N., Kenyon, C., Mossel, E. and Peres, Y. (2005). Glauber dynamics on prob and hyperbolic graphs. Probab. Theory Related Fields 131 311-340. · Zbl 1075.60003
[3] Cesi, F. (2001). Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probab. Theory Related Fields 120 569-584. · Zbl 1086.82002
[4] Dembo, A. and Montanari, A. (2010). Ising models on locally tree-like graphs. Ann. Appl. Probab. 20 565-592. · Zbl 1191.82025
[5] Dobrushin, R. L. and Shlosman, S. B. (1985). Constructive criterion for uniqueness of a Gibbs field. In Statistical Mechanics and Dynamical Systems , Volume 10 (J. Fritz, A. Jaffe and D. Szasz, eds.) 347-370. · Zbl 0569.46042
[6] Dyer, M., Sinclair, A., Vigoda, E. and Weitz, D. (2004). Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures Algorithms 24 461-479. · Zbl 1126.82021
[7] Gershchenfeld, A. and Montanari, A. (2007). Reconstruction for models on random graphs. In Annual IEEE Symposium on Foundations of Computer Science 194-204. IEEE Comput. Soc., Los Alamitos, CA.
[8] Hayes, T. P. and Sinclair, A. (2007). A general lower bound for mixing of single-site dynamics on graphs. Ann. Appl. Probab. 17 931-952. · Zbl 1125.60075
[9] Hayes, T. P. and Vigoda, E. (2006). Coupling with the stationary distribution and improved sampling for colorings and independent sets. Ann. Appl. Probab. 16 1297-1318. · Zbl 1120.60067
[10] Higuchi, Y. (1993). Coexistence of infinite (\ast )-clusters II. Ising percolation in two dimensions. Probab. Theory Related Fields 97 1-33. · Zbl 0794.60102
[11] Jerrum, M. and Sinclair, A. (1989). Approximating the permanent. SIAM J. Comput. 18 1149-1178. · Zbl 0723.05107
[12] Kenyon, C., Mossel, E. and Peres, Y. (2001). Glauber dynamics on trees and hyperbolic graphs. In 42 nd IEEE Symposium on Foundations of Computer Science ( Las Vegas , NV ) 568-578. IEEE Comput. Soc., Los Alamitos, CA. · Zbl 1075.60003
[13] Krząkała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104 10318-10323. · Zbl 1190.68031
[14] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times . Amer. Math. Soc., Providence, RI. With a chapter by James G. Propp and David B. Wilson. · Zbl 1160.60001
[15] Liggett, T. M. (1985). Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften [ Fundamental Principles of Mathematical Sciences ] 276 . Springer, New York. · Zbl 0559.60078
[16] Lyons, R. (1989). The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys. 125 337-353. · Zbl 0679.60101
[17] Martinelli, F. (1999). Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics. Lecture Notes in Math. 1717 93-191. Springer, Berlin. · Zbl 1051.82514
[18] Martinelli, F. and Olivieri, E. (1994). Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161 447-486. · Zbl 0793.60110
[19] Martinelli, F. and Olivieri, E. (1994). Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case. Comm. Math. Phys. 161 487-514. · Zbl 0793.60111
[20] Martinelli, F., Sinclair, A. and Weitz, D. (2003). The Ising model on trees: Boundary conditions and mixing time. In Proceedings of the Forty Fourth Annual Symposium on Foundations of Computer Science 628-639.
[21] Martinelli, F., Sinclair, A. A. and Weitz, D. (2004). Glauber dynamics on trees: Boundary conditions and mixing time. Comm. Math. Phys. 250 301-334. · Zbl 1076.82010
[22] Mézard, M. and Montanari, A. (2009). Information , Physics , and Computation . Oxford Univ. Press, Oxford. · Zbl 1163.94001
[23] Montanari, A., Ricci-Tersenghi, F. and Semerjian, G. (2008). Clusters of solutions and replica symmetry breaking in random k-satisfiability. J. Stat. Mech. Theory Exp. 2008 P04004.
[24] Mossel, E. and Sly, A. (2008). 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 ) 238-247. · Zbl 1193.65012
[25] Mossel, E. and Sly, A. (2009). Rapid mixing of Gibbs sampling on graphs that are sparse on average. Random Structures Algorithms 35 250-270. · Zbl 1216.60054
[26] Mossel, E., Weitz, D. and Wormald, N. (2009). On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Related Fields 143 401-439. · Zbl 1165.60028
[27] Peres, Y. Mixing for Markov chains and spin systems. Draft lecture notes.
[28] Stroock, D. W. and Zegarliński, B. (1992). The logarithmic Sobolev inequality for discrete spin systems on a lattice. Comm. Math. Phys. 149 175-193. · Zbl 0758.60070
[29] Vigoda, E. (1999). Improved bounds for sampling coloring. In 40 th Annual Symposium on Foundations of Computer Science ( FOCS ) 51-59. · Zbl 0978.60083
[30] Vigoda, E. (2000). Improved bounds for sampling coloring. J. Math. Phys. 3 1555-1569. · Zbl 0978.60083
[31] Weitz, D. (2005). Combinatorial criteria for uniqueness of Gibbs measures. Random Structures Algorithms 27 445-475. · Zbl 1095.82006
[32] Weitz, D. (2006). Counting indpendent sets up to the tree threshold. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing 140-149. ACM, New York. · Zbl 1301.68276
[33] Zhang, J., Liang, H. and Bai, F. (2011). Approximating partition functions of the two-state spin system. Inform. Process. Lett. 111 702-710. · Zbl 1260.68469
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.