Random-cluster dynamics in \(\mathbb{Z}^2\): Rapid mixing with general boundary conditions. (English) Zbl 07650134
Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 67, 19 p. (2019).
Summary: The random-cluster (FK) model is a key tool for the study of phase transitions and for the design of efficient Markov chain Monte Carlo (MCMC) sampling algorithms for the Ising/Potts model. It is well-known that in the high-temperature region \(\beta<\beta_c(q)\) of the \(q\)-dtate Ising/Potts model on an \(n\times n\) box \(\Lambda_n\) of the integer lattice \(\mathbb{Z}^2\), spin correlations decay exponentially fast; this property holds even arbitrarily close to the boundary of \(\Lambda_n\) and uniformly over all boundary conditions. A direct consequence of this property is that the corresponding single-site update Markov chain, known as the Glauber dynamics, mixes in optimal \(O(n^2\log n)\) steps on \(\Lambda_n\) for all choices of boundary conditions. We study the effect of boundary conditions on the FK-dynamics, the analogous Glauber dynamics for the random-cluster model.
On \(\Lambda_n\) the random-cluster model with parameters \((p,q)\) has a sharp phase transition at \(p= p_c(q)\). Unlike the Ising/Potts model, the random-cluster model has non-local interactions which can be forced by boundary conditions: external wirings of boundary vertices of \(\Lambda_n\). We consider the broad and natural class of boundary conditions that are realizable as a configuration on \(\mathbb{Z}^2\setminus\Lambda_n\). Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures \((p\ll p_c(q))\). In this paper, we prove that when \(q>1\) and \(p\ne p_c(q)\) the mixing time of the FK-dynamics is polynomial in \(n\) for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), A. Blanca and A. Sinclair [LIPIcs – Leibniz Int. Proc. Inform. 40, 528–543 (2015; Zbl 1375.60133)] had proved that the FK-dynamics in the same setting mixes in optimal \(O(n^2\log n)\) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.
For the entire collection see [Zbl 1423.68013].
On \(\Lambda_n\) the random-cluster model with parameters \((p,q)\) has a sharp phase transition at \(p= p_c(q)\). Unlike the Ising/Potts model, the random-cluster model has non-local interactions which can be forced by boundary conditions: external wirings of boundary vertices of \(\Lambda_n\). We consider the broad and natural class of boundary conditions that are realizable as a configuration on \(\mathbb{Z}^2\setminus\Lambda_n\). Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures \((p\ll p_c(q))\). In this paper, we prove that when \(q>1\) and \(p\ne p_c(q)\) the mixing time of the FK-dynamics is polynomial in \(n\) for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), A. Blanca and A. Sinclair [LIPIcs – Leibniz Int. Proc. Inform. 40, 528–543 (2015; Zbl 1375.60133)] had proved that the FK-dynamics in the same setting mixes in optimal \(O(n^2\log n)\) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.
For the entire collection see [Zbl 1423.68013].
Citations:
Zbl 1375.60133References:
| [1] | Kenneth S. Alexander. On weak mixing in lattice models. Probab. Theory Related Fields, 110(4):441-471, 1998. doi:10.1007/s004400050155. · Zbl 0906.60074 · doi:10.1007/s004400050155 |
| [2] | Vincent Beffara and Hugo Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1. Probab. Theory Related Fields, 153(3-4):511-542, 2012. doi:10.1007/s00440-011-0353-8. · Zbl 1257.82014 · doi:10.1007/s00440-011-0353-8 |
| [3] | Antonio Blanca, Reza Gheissari, and Eric Vigoda. Random-cluster dynamics in Z 2 : rapid mixing with general boundary conditions. preprint available at arXiv:1807.08722., 2018. · Zbl 1434.60273 |
| [4] | Antonio Blanca and Alistair Sinclair. Dynamics for the Mean-field Random-cluster Model. In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015), pages 528-543, 2015. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.528. · Zbl 1375.60133 · doi:10.4230/LIPIcs.APPROX-RANDOM.2015.528 |
| [5] | Antonio Blanca and Alistair Sinclair. Random-Cluster Dynamics in Z 2 . Probab. Theory Related Fields, 2016. Extended abstract appeared in Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 498-513. doi:10.1007/s00440-016-0725-1. · Zbl 1369.60067 · doi:10.1007/s00440-016-0725-1 |
| [6] | Christian Borgs, Jennifer T. Chayes, Alan Frieze, Jeong H. Kim, Prasad Tetali, Eric Vigoda, and Van H. Vu. Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In Proc. of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), pages 218-229, 1999. doi:10.1109/SFFCS.1999.814594. · doi:10.1109/SFFCS.1999.814594 |
| [7] | Christian Borgs, Jennifer T. Chayes, and Prasad Tetali. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Related Fields, 152(3-4):509-557, 2012. doi:10.1007/s00440-010-0329-0. · Zbl 1250.60034 · doi:10.1007/s00440-010-0329-0 |
| [8] | APPROX/RANDOM 2019 67:18 Random-Cluster Dynamics in Z 2 : Rapid Mixing with General Boundary Conditions |
| [9] | Filippo Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probability Theory and Related Fields, 120(4):569-584, August 2001. doi:10.1007/PL00008792. · Zbl 1086.82002 · doi:10.1007/PL00008792 |
| [10] | Lincoln Chayes and Jon Machta. Graphical representations and cluster algorithms I. Discrete spin systems. Physica A: Statistical Mechanics and its Applications, 239(4):542-601, 1997. |
| [11] | Colin Cooper and Alan M. Frieze. Mixing properties of the Swendsen-Wang process on classes of graphs. Random Structures and Algorithms, 15:242-261, 1999. · Zbl 0945.82003 |
| [12] | Hugo Duminil Copin, Maxim Gagnebin, Matan Harel, Ioan Manolescu, and Vincent Tassion. Discontinuity of the phase transition for the planar random-cluster and Potts models with q > 4. CoRR, 2016. arXiv:1611.09877. |
| [13] | Hugo Duminil-Copin, Vladas Sidoravicius, and Vincent Tassion. Continuity of the Phase Transition for Planar Random-Cluster and Potts Models with 1 ≤ q ≤ 4. Communications in Mathematical Physics, 349(1):47-107, January 2017. doi:10.1007/s00220-016-2759-8. · Zbl 1357.82011 · doi:10.1007/s00220-016-2759-8 |
| [14] | Cornelius M. Fortuin and Pieter W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57:536-564, 1972. |
| [15] | Andreas Galanis, Daniel Štefankovic, and Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model. In Proc. of the 19th International Workshop on Randomization and Computation (RANDOM 2015), pages 815-828, 2015. doi:10.4230/LIPIcs.APPROX-RANDOM. 2015.815. · Zbl 1375.82019 · doi:10.4230/LIPIcs.APPROX-RANDOM.2015.815 |
| [16] | Shirshendu Ganguly and Insuk Seo. Information Percolation and Cutoff for the Random-Cluster Model. CoRR, 2018. arXiv:1812.01538. · Zbl 1453.82077 |
| [17] | Reza Gheissari and Eyal Lubetzky. Mixing Times of Critical Two-Dimensional Potts Models. Comm. Pure Appl. Math, 71(5):994-1046, 2018. · Zbl 1392.82007 |
| [18] | Reza Gheissari and Eyal Lubetzky. The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions. Electron. J. Probab., 23:30 pp., 2018. doi:10.1214/18-EJP180. · Zbl 1410.60092 · doi:10.1214/18-EJP180 |
| [19] | Reza Gheissari and Eyal Lubetzky. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures and Algorithms, 2019. doi:10.1002/rsa.20868. · Zbl 1453.82043 · doi:10.1002/rsa.20868 |
| [20] | Reza Gheissari, Eyal Lubetzky, and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. Annales de l’Institut Henri Poincare (B), 2019. to appear. Extended abstract appeared in Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1981-1988. · Zbl 1403.60063 |
| [21] | Vivek K. Gore and Mark R. Jerrum. The Swendsen-Wang process does not always mix rapidly. J. Statist. Phys., 97(1-2):67-86, 1999. doi:10.1023/A:1004610900745. · Zbl 1006.82015 · doi:10.1023/A:1004610900745 |
| [22] | Geoffrey Grimmett. The random-cluster model. In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 73-123. Springer, Berlin, 2004. doi: 10.1007/978-3-662-09444-0_2. · Zbl 1045.60105 · doi:10.1007/978-3-662-09444-0_2 |
| [23] | Heng Guo and Mark Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1818-1827, 2017. doi:10.1137/1.9781611974782.118. · Zbl 1419.82013 · doi:10.1137/1.9781611974782.118 |
| [24] | Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. doi:10.1137/0218077. · Zbl 0723.05107 · doi:10.1137/0218077 |
| [25] | David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Related Fields, 146(1-2):223-265, 2010. doi:10.1007/s00440-008-0189-z. · Zbl 1187.82076 · doi:10.1007/s00440-008-0189-z |
| [26] | Eyal Lubetzky, Fabio Martinelli, Allan Sly, and Fabio Lucio Toninelli. Quasi-polynomial mixing of the 2D stochastic Ising model with “plus” boundary up to criticality. J. Eur. Math. Soc. (JEMS), 15(2):339-386, 2013. doi:10.4171/JEMS/363. · Zbl 1266.60161 · doi:10.4171/JEMS/363 |
| [27] | Fabio Martinelli. On the two-dimensional dynamical Ising model in the phase coexistence region. J. Statist. Phys., 76(5-6):1179-1246, 1994. doi:10.1007/BF02187060. 67:19 · Zbl 0839.60087 · doi:10.1007/BF02187060 |
| [28] | Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997), volume 1717 of Lecture Notes in Math., pages 93-191. Springer, Berlin, 1999. doi:10.1007/978-3-540-48115-7_2. · Zbl 1051.82514 · doi:10.1007/978-3-540-48115-7_2 |
| [29] | Fabio Martinelli, Enzo Olivieri, and Roberto H. Schonmann. For 2-D lattice spin systems weak mixing implies strong mixing. Comm. Math. Phys., 165(1):33-47, 1994. URL: http: //projecteuclid.org/euclid.cmp/1104271032. · Zbl 0811.60097 |
| [30] | Fabio Martinelli and Fabio Lucio Toninelli. On the mixing time of the 2D stochastic Ising model with “plus” boundary conditions at low temperature. Comm. Math. Phys., 296(1):175-213, 2010. doi:10.1007/s00220-009-0963-5. · Zbl 1191.82012 · doi:10.1007/s00220-009-0963-5 |
| [31] | Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294-328, January 2013. doi:10.1214/11-AOP737. · Zbl 1270.60113 · doi:10.1214/11-AOP737 |
| [32] | Lars Onsager. Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition. Phys. Rev., 65:117-149, February 1944. doi:10.1103/PhysRev.65.117. · Zbl 0060.46001 · doi:10.1103/PhysRev.65.117 |
| [33] | Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput., 1(4):351-370, 1992. doi:10.1017/S0963548300000390. · Zbl 0801.90039 · doi:10.1017/S0963548300000390 |
| [34] | Robert H. Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett., 58:86-88, January 1987. doi:10.1103/PhysRevLett.58.86. · doi:10.1103/PhysRevLett.58.86 |
| [35] | Lawrence E. Thomas. Bound on the mass gap for finite volume stochastic Ising models at low temperature. Comm. Math. Phys., 126(1):1-11, 1989. URL: http://projecteuclid.org/ euclid.cmp/1104179720. · Zbl 0679.60102 |
| [36] | Mario Ullrich. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures and Algorithms, 42(4):520-535, 2013. doi:10.1002/rsa.20431. · Zbl 1272.82009 · doi:10.1002/rsa.20431 |
| [37] | Mario Ullrich. Rapid mixing of Swendsen-Wang dynamics in two dimensions. Dissertationes Math. (Rozprawy Mat.), 502:64, 2014. doi:10.4064/dm502-0-1. · Zbl 1315.60113 · doi:10.4064/dm502-0-1 |
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.
