Random cluster dynamics for the Ising model is rapidly mixing. (English) Zbl 1395.82133
Summary: We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at \(q=2\) on an arbitrary \(n\)-vertex graph is bounded by a polynomial in \(n\). As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.
MSC:
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
| 82D40 | Statistical mechanics of magnetic materials |
References:
| [1] | Blanca, A. and Sinclair, A. (2015). Dynamics for the mean-field random-cluster model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LIPIcs. Leibniz Int. Proc. Inform.40 528-543. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. · Zbl 1375.60133 |
| [2] | Blanca, A. and Sinclair, A. (2016). Random-cluster dynamics in \(\mathbb{Z}^{2}\). Probab. Theory Relat. Fields. DOI:10.1007/s00440-016-0725-1. · Zbl 1419.82007 |
| [3] | Bollobás, B., Grimmett, G. and Janson, S. (1996). The random-cluster model on the complete graph. Probab. Theory Related Fields 104 283-317. · Zbl 0846.05075 · doi:10.1007/BF01213683 |
| [4] | Borgs, C., Chayes, J. T., Frieze, A., Kim, J. H., Tetali, P., Vigoda, E. and Vu, V. H. (1999). Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In 40 th Annual Symposium on Foundations of Computer Science (New York, 1999) 218-229. IEEE Computer Soc., Los Alamitos, CA. |
| [5] | Cai, J.-Y., Guo, H. and Williams, T. (2016). A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput.45 1671-1728. · Zbl 1350.68133 · doi:10.1137/15M1049798 |
| [6] | Collevecchio, A., Garoni, T. M., Hyndman, T. and Tokarev, D. (2016). The worm process for the Ising model is rapidly mixing. J. Stat. Phys.164 1082-1102. · Zbl 1362.82006 · doi:10.1007/s10955-016-1572-2 |
| [7] | Diaconis, P. and Saloff-Coste, L. (1993). Comparison theorems for reversible Markov chains. Ann. Appl. Probab.3 696-730. · Zbl 0799.60058 · doi:10.1214/aoap/1177005359 |
| [8] | Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab.1 36-61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980 |
| [9] | Duminil-Copin, H., Gagnebin, M., Harel, M., Manolescu, I. and Tassion, V. (2016). Discontinuity of the phase transition for the planar random-cluster and Potts models with \(q>4\). Available at arXiv:abs/1611.09877. |
| [10] | Dyer, M., Goldberg, L. A., Jerrum, M. and Martin, R. (2006). Markov chain comparison. Probab. Surv.3 89-111. · Zbl 1189.60135 · doi:10.1214/154957806000000041 |
| [11] | Edwards, R. G. and Sokal, A. D. (1988). Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D 38 2009-2012. |
| [12] | Fortuin, C. M. and Kasteleyn, P. W. (1972). On the random-cluster model. I. Introduction and relation to other models. Physica 57 536-564. |
| [13] | Galanis, A., Štefankovič, D. and Vigoda, E. (2015). Swendsen-Wang algorithm on the mean-field Potts model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LIPIcs. Leibniz Int. Proc. Inform.40 815-828. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. · Zbl 1375.82019 |
| [14] | Gheissari, R. and Lubetzky, E. (2016). Mixing times of critical 2D Potts models. Available at arXiv:abs/1607.02182. |
| [15] | Goldberg, L. A. and Jerrum, M. (2008). Inapproximability of the Tutte polynomial. Inform. and Comput.206 908-929. · Zbl 1153.68039 · doi:10.1016/j.ic.2008.04.003 |
| [16] | Goldberg, L. A. and Jerrum, M. (2012). Approximating the partition function of the ferromagnetic Potts model. J. ACM 59 Art. 25, 31. · Zbl 1281.68116 · doi:10.1145/2371656.2371660 |
| [17] | Goldberg, L. A. and Jerrum, M. (2014). The complexity of computing the sign of the Tutte polynomial. SIAM J. Comput.43 1921-1952. · Zbl 1437.68068 |
| [18] | Gore, V. K. and Jerrum, M. R. (1999). The Swendsen-Wang process does not always mix rapidly. J. Stat. Phys.97 67-86. · Zbl 1006.82015 · doi:10.1023/A:1004610900745 |
| [19] | Grimmett, G. (2006). The Random-Cluster Model. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 333. Springer, Berlin. · Zbl 1122.60087 |
| [20] | Grimmett, G. and Janson, S. (2009). Random even graphs. Electron. J. Combin.16 Research Paper, 46, 19. · Zbl 1214.05155 |
| [21] | Jerrum, M. and Sinclair, A. (1989). Approximating the permanent. SIAM J. Comput.18 1149-1178. · Zbl 0723.05107 · doi:10.1137/0218077 |
| [22] | Jerrum, M. and Sinclair, A. (1993). Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput.22 1087-1116. · Zbl 0782.05076 · doi:10.1137/0222066 |
| [23] | Long, Y., Nachmias, A., Ning, W. and Peres, Y. (2014). A power law of order \(1/4\) for critical mean field Swendsen-Wang dynamics. Mem. Am. Math. Soc.232. · Zbl 1304.60078 |
| [24] | Lubetzky, E. and Sly, A. (2012). Critical Ising on the square lattice mixes in polynomial time. Comm. Math. Phys.313 815-836. · Zbl 1250.82008 · doi:10.1007/s00220-012-1460-9 |
| [25] | Peres, Y. (2017). Personal communication. |
| [26] | Prokof’ev, N. and Svistunov, B. (2001). Worm algorithms for classical statistical models. Phys. Rev. Lett.87 160601. |
| [27] | Randall, D. and Wilson, D. (1999). Sampling spin configurations of an Ising system. In SODA 959-960. · Zbl 1052.82525 |
| [28] | Sinclair, A. (1992). Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput.1 351-370. · Zbl 0801.90039 · doi:10.1017/S0963548300000390 |
| [29] | Sinclair, A. and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput.82 93-133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9 |
| [30] | Swendsen, R. and Wang, J.-S. (1987). Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett.58 86-88. |
| [31] | Ullrich, M. (2013). Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures Algorithms 42 520-535. · Zbl 1272.82009 · doi:10.1002/rsa.20431 |
| [32] | Ullrich, M. (2014a). Rapid mixing of Swendsen-Wang dynamics in two dimensions. Dissertationes Math. (Rozprawy Mat.) 502. · Zbl 1315.60113 · doi:10.4064/dm502-0-1 |
| [33] | Ullrich, M. (2014b). Swendsen-Wang is faster than single-bond dynamics. SIAM J. Discrete Math.28 37-48. · Zbl 1294.60120 · doi:10.1137/120864003 |
| [34] | van der Waerden, B. L. (1941). Die lange Reichweite der regelmäßigen Atomanordnung in Mischkristallen. Z. Phys.118 473-488. · Zbl 0026.28301 · doi:10.1007/BF01342928 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
