Document Open Access Logo

Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions

Authors Antonio Blanca, Reza Gheissari, Eric Vigoda

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.67.pdf
  • Filesize: 0.59 MB
  • 19 pages

Document Identifiers

Author Details

Antonio Blanca
  • Department of Computer Science and Engineering, Pennsylvania State University, USA
Reza Gheissari
  • Courant Institute of Mathematical Sciences, New York University, USA
Eric Vigoda
  • School of Computer Science, Georgia Institute of Technology, USA

Funding

  • Blanca, Antonio: Research supported in part by NSF grants CCF-1617306 and CCF-1563838.
  • Vigoda, Eric: Research supported in part by NSF grants CCF-1617306 and CCF-1563838.

Acknowledgements

The authors thank the anonymous referees for their helpful suggestions.

Cite As Get BibTex

Antonio Blanca, Reza Gheissari, and Eric Vigoda. Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.67

Abstract

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-state Ising/Potts model on an n x n box Lambda_n of the integer lattice 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 Z^2 \ Lambda_n. Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures (p << p_c(q)). In this paper, we prove that when q>1 and p != 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), Blanca and Sinclair (2017) 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Markov-chain Monte Carlo convergence measures
  • Theory of computation → Random walks and Markov chains
Keywords
  • Markov chain
  • mixing time
  • random-cluster model
  • Glauber dynamics
  • spatial mixing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Kenneth S. Alexander. On weak mixing in lattice models. Probab. Theory Related Fields, 110(4):441-471, 1998. URL: https://doi.org/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. URL: https://doi.org/10.1007/s00440-011-0353-8.
  3. Antonio Blanca, Reza Gheissari, and Eric Vigoda. Random-cluster dynamics in ℤ²: rapid mixing with general boundary conditions. preprint available at https://arxiv.org/abs/1807.08722., 2018.
  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. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.528.
  5. Antonio Blanca and Alistair Sinclair. Random-Cluster Dynamics in ℤ². 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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1007/s00440-010-0329-0.
  8. 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. URL: https://doi.org/10.1007/PL00008792.
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. 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. URL: http://arxiv.org/abs/1611.09877.
  12. 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. URL: https://doi.org/10.1007/s00220-016-2759-8.
  13. Cornelius M. Fortuin and Pieter W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57:536-564, 1972. Google Scholar
  14. 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. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.815.
  15. Shirshendu Ganguly and Insuk Seo. Information Percolation and Cutoff for the Random-Cluster Model. CoRR, 2018. URL: http://arxiv.org/abs/1812.01538.
  16. Reza Gheissari and Eyal Lubetzky. Mixing Times of Critical Two-Dimensional Potts Models. Comm. Pure Appl. Math, 71(5):994-1046, 2018. Google Scholar
  17. 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. URL: https://doi.org/10.1214/18-EJP180.
  18. Reza Gheissari and Eyal Lubetzky. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures and Algorithms, 2019. URL: https://doi.org/10.1002/rsa.20868.
  19. 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. Google Scholar
  20. 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. URL: https://doi.org/10.1023/A:1004610900745.
  21. Geoffrey Grimmett. The random-cluster model. In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 73-123. Springer, Berlin, 2004. URL: https://doi.org/10.1007/978-3-662-09444-0_2.
  22. 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. URL: https://doi.org/10.1137/1.9781611974782.118.
  23. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. URL: https://doi.org/10.1137/0218077.
  24. 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. URL: https://doi.org/10.1007/s00440-008-0189-z.
  25. 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. URL: https://doi.org/10.4171/JEMS/363.
  26. Fabio Martinelli. On the two-dimensional dynamical Ising model in the phase coexistence region. J. Statist. Phys., 76(5-6):1179-1246, 1994. URL: https://doi.org/10.1007/BF02187060.
  27. 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. URL: https://doi.org/10.1007/978-3-540-48115-7_2.
  28. 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.
  29. 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. URL: https://doi.org/10.1007/s00220-009-0963-5.
  30. Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294-328, January 2013. URL: https://doi.org/10.1214/11-AOP737.
  31. Lars Onsager. Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition. Phys. Rev., 65:117-149, February 1944. URL: https://doi.org/10.1103/PhysRev.65.117.
  32. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput., 1(4):351-370, 1992. URL: https://doi.org/10.1017/S0963548300000390.
  33. Robert H. Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett., 58:86-88, January 1987. URL: https://doi.org/10.1103/PhysRevLett.58.86.
  34. 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.
  35. Mario Ullrich. Comparison of Swendsen-Wang and heat-bath dynamics. Random Structures and Algorithms, 42(4):520-535, 2013. URL: https://doi.org/10.1002/rsa.20431.
  36. Mario Ullrich. Rapid mixing of Swendsen-Wang dynamics in two dimensions. Dissertationes Math. (Rozprawy Mat.), 502:64, 2014. URL: https://doi.org/10.4064/dm502-0-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact