zbMATH — the first resource for mathematics

Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions. (English) Zbl 1434.60273
Summary: The random-cluster model with parameters \((p,q)\) is a random graph model that generalizes bond percolation \((q=1)\) and the Ising and Potts models \((q\geq 2)\). We study its Glauber dynamics on \(n\times n\) boxes \(\Lambda_n\) of the integer lattice graph \(\mathbb{Z}^2\), where the model exhibits a sharp phase transition at \(p=p_c(q)\). Unlike traditional spin systems like the Ising and Potts models, the random-cluster model has non-local interactions. Long-range interactions can be imposed as external connections in the boundary of \(\Lambda_n\), known as boundary conditions. For select boundary conditions that do not carry long-range information (namely, wired and free), Blanca and Sinclair proved that when \(q>1\) and \(p\neq p_c(q)\), the Glauber dynamics on \(\Lambda_n\) mixes in optimal \(O(n^2\log n)\) time. In this paper, we prove that this mixing time is polynomial in \(n\) for every boundary condition that is realizable as a configuration on \(\mathbb{Z}^2\setminus\Lambda_n\). We then use this to prove near-optimal \(\tilde{O}(n^2)\) mixing time for “typical” boundary conditions. As a complementary result, we construct classes of nonrealizable (nonplanar) boundary conditions inducing slow (stretched-exponential) mixing at \(p\ll p_c\).

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
Full Text: DOI Euclid
[1] Alexander, K. S. (2004). Mixing properties and exponential decay for lattice systems in finite volumes. Ann. Probab. 32 441-487. · Zbl 1048.60080
[2] Beffara, V. and Duminil-Copin, H. (2012). The self-dual point of the two-dimensional random-cluster model is critical for \(q\geq 1\). Probab. Theory Related Fields 153 511-542. · Zbl 1257.82014
[3] 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
[4] Blanca, A. and Sinclair, A. (2017). Random-cluster dynamics in \(\mathbb{Z}^2 \). Probab. Theory Related Fields 168 821-847. · Zbl 1369.60067
[5] 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 40th Annual Symposium on Foundations of Computer Science (New York, 1999) 218-229. IEEE Computer Soc., Los Alamitos, CA.
[6] Borgs, C., Chayes, J. T. and Tetali, P. (2012). Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Related Fields 152 509-557. · Zbl 1250.60034
[7] 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
[8] Chayes, L. and Machta, J. (1998). Graphical representations and cluster algorithms II. Phys. A 254 477-516.
[9] Cooper, C. and Frieze, A. M. (1999). Mixing properties of the Swendsen-Wang process on classes of graphs. Random Structures Algorithms 15 242-261. · Zbl 0945.82003
[10] Duminil-Copin, H. and Manolescu, I. (2016). The phase transitions of the planar random-cluster and Potts models with \(q\ge1\) are sharp. Probab. Theory Related Fields 164 865-892. · Zbl 1356.60167
[11] Duminil-Copin, H., Sidoravicius, V. and Tassion, V. (2017). Continuity of the phase transition for planar random-cluster and Potts models with \(1\leq q\leq 4\). Comm. Math. Phys. 349 47-107. · Zbl 1357.82011
[12] 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.
[13] Fortuin, C. M. and Kasteleyn, P. W. (1972). On the random-cluster model. I. Introduction and relation to other models. Physica 57 536-564.
[14] 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
[15] Ganguly, S. and Seo, I. (2018). Information percolation and cutoff for the random-cluster model. Preprint. Available at arXiv:1812.01538.
[16] Gheissari, R. and Lubetzky, E. (2018). Mixing times of critical two-dimensional Potts models. Comm. Pure Appl. Math. 71 994-1046. · Zbl 1392.82007
[17] Gheissari, R. and Lubetzky, E. (2019). Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures and Algorithms. · Zbl 1392.82007
[18] Gheissari, R. and Lubetzky, E. (2018). The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions. Electron. J. Probab. 23 Paper No. 57, 30. · Zbl 1410.60092
[19] Gheissari, R., Lubetzky, E. and Peres, Y. (2018). Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms 1981-1988. SIAM, Philadelphia, PA. · Zbl 1403.60063
[20] 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
[21] Grimmett, G. (2006). The Random-Cluster Model. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 333. Springer, Berlin. · Zbl 1122.60087
[22] Guo, H. and Jerrum, M. (2018). Random cluster dynamics for the Ising model is rapidly mixing. Ann. Appl. Probab. 28 1292-1313. · Zbl 1395.82133
[23] Jerrum, M. and Sinclair, A. (1989). Approximating the permanent. SIAM J. Comput. 18 1149-1178. · Zbl 0723.05107
[24] Levin, D. A. and Peres, Y. (2017). Markov Chains and Mixing Times, 2nd ed. Amer. Math. Soc., Providence, RI.
[25] Lubetzky, E., Martinelli, F., Sly, A. and Toninelli, F. L. (2013). Quasi-polynomial mixing of the 2D stochastic Ising model with “plus” boundary up to criticality. J. Eur. Math. Soc. (JEMS) 15 339-386. · Zbl 1266.60161
[26] Martinelli, F. (1994). On the two-dimensional dynamical Ising model in the phase coexistence region. J. Stat. Phys. 76 1179-1246. · Zbl 0839.60087
[27] Martinelli, F. (1999). Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics (Saint-Flour, 1997). Lecture Notes in Math. 1717 93-191. Springer, Berlin. · Zbl 1051.82514
[28] Martinelli, F., Olivieri, E. and Schonmann, R. H. (1994). For \(2\)-D lattice spin systems weak mixing implies strong mixing. Comm. Math. Phys. 165 33-47. · Zbl 0811.60097
[29] Martinelli, F. and Toninelli, F. L. (2010). On the mixing time of the 2D stochastic Ising model with “plus” boundary conditions at low temperature. Comm. Math. Phys. 296 175-213. · Zbl 1191.82012
[30] Mossel, E. and Sly, A. (2013). Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab. 41 294-328. · Zbl 1270.60113
[31] Onsager, L. (1944). Crystal statistics. I. A two-dimensional model with an order-disorder transition. Phys. Rev. 65 117-149. · Zbl 0060.46001
[32] Saloff-Coste, L. (1997). Lectures on finite Markov chains. In Lectures on Probability Theory and Statistics (Saint-Flour, 1996). Lecture Notes in Math. 1665 301-413. Springer, Berlin. · Zbl 0885.60061
[33] Sinclair, A. (1992). Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351-370. · Zbl 0801.90039
[34] Swendsen, R. H. and Wang, J. S. (1987). Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58 86-88.
[35] Thomas, L. E. (1989). Bound on the mass gap for finite volume stochastic Ising models at low temperature. Comm. Math. Phys. 126 1-11. · Zbl 0679.60102
[36] Ullrich, M. (2013). Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures Algorithms 42 520-535. · Zbl 1272.82009
[37] Ullrich, M. (2014). Swendsen-Wang is faster than single-bond dynamics. SIAM J. Discrete Math. 28 37-48. · Zbl 1294.60120
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.