Document Open Access Logo

Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2

Author Tianyu Liu

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.52.pdf
  • Filesize: 4.18 MB
  • 15 pages

Document Identifiers

Author Details

Tianyu Liu
  • University of Wisconsin-Madison, Madison, WI, USA

Funding

This work was supported by NSF CCF-1714275.

Cite AsGet BibTex

Tianyu Liu. Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.52

Abstract

In this paper, we study the mixing time of two widely used Markov chain algorithms for the six-vertex model, Glauber dynamics and the directed-loop algorithm, on the square lattice Z^2. We prove, for the first time that, on finite regions of the square lattice these Markov chains are torpidly mixing under parameter settings in the ferroelectric phase and the anti-ferroelectric phase.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Random walks and Markov chains
Keywords
  • the six-vertex model
  • Eulerian orientations
  • square lattice
  • torpid mixing

Metrics

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

References

  1. David Allison and Nicolai Reshetikhin. Numerical study of the 6-vertex model with domain wall boundary conditions. Annales de l'Institut Fourier, 55(6):1847-1869, 2005. URL: http://eudml.org/doc/116236.
  2. G. T. Barkema and M. E. J. Newman. Monte Carlo simulation of ice models. Phys. Rev. E, 57:1155-1166, Jan 1998. URL: http://dx.doi.org/10.1103/PhysRevE.57.1155.
  3. R. J. Baxter. Exactly Solved Models in Statistical Mechanics. Academic Press, 1982. URL: http://dx.doi.org/10.1007/978-3-642-73193-8_19.
  4. Antonio Blanca, David Galvin, Dana Randall, and Prasad Tetali. Phase coexistence and slow mixing for the hard-core model on ℤ². In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 379-394, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_27.
  5. Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, Alan Frieze, Prasad Tetali, Eric Vigoda, and Van Ha Vu. Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 218-229, 1999. URL: http://dl.acm.org/citation.cfm?id=795665.796518.
  6. H. J. Brascamp, H. Kunz, and F. Y. Wu. Some rigorous results for the vertex model in statistical mechanics. Journal of Mathematical Physics, 14(12):1927-1932, 1973. URL: http://dx.doi.org/10.1063/1.1666271.
  7. Jin-Yi Cai, Tianyu Liu, and Pinyan Lu. Approximability of the six-vertex model. CoRR, abs/1712.05880, 2017. URL: http://arxiv.org/abs/1712.05880.
  8. F. Cesi, G. Guadagni, F. Martinelli, and R. H. Schonmann. On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point. Journal of Statistical Physics, 85(1):55-102, Oct 1996. URL: http://dx.doi.org/10.1007/BF02175556.
  9. K. Eloranta. Diamond Ice. Journal of Statistical Physics, 96:1091-1109, 1999. URL: http://dx.doi.org/10.1023/A:1004644418182.
  10. Chungpeng Fan and F. Y. Wu. General lattice model of phase transitions. Phys. Rev. B, 2:723-733, Aug 1970. URL: http://dx.doi.org/10.1103/PhysRevB.2.723.
  11. Leslie Ann Goldberg, Russell Martin, and Mike Paterson. Random sampling of 3-colorings in ℤ². Random Structures &Algorithms, 24(3):279-302, 2004. URL: http://dx.doi.org/10.1002/rsa.20002.
  12. A.J. Guttmann and A.R. Conway. Square lattice self-avoiding walks and polygons. Annals of Combinatorics, 5(3):319-345, Dec 2001. URL: http://dx.doi.org/10.1007/PL00013842.
  13. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006. Google Scholar
  14. Elliott H. Lieb. Exact solution of the F model of an antiferroelectric. Phys. Rev. Lett., 18:1046-1048, Jun 1967. URL: http://dx.doi.org/10.1103/PhysRevLett.18.1046.
  15. Elliott H. Lieb. Exact solution of the two-dimensional Slater KDP model of a ferroelectric. Phys. Rev. Lett., 19:108-110, Jul 1967. URL: http://dx.doi.org/10.1103/PhysRevLett.19.108.
  16. Elliott H. Lieb. Residual entropy of square ice. Phys. Rev., 162:162-172, Oct 1967. URL: http://dx.doi.org/10.1103/PhysRev.162.162.
  17. Eyal Lubetzky and Allan Sly. Critical Ising on the square lattice mixes in polynomial time. Communications in Mathematical Physics, 313(3):815-836, Aug 2012. URL: http://dx.doi.org/10.1007/s00220-012-1460-9.
  18. Michael Luby, Dana Randall, and Alistair Sinclair. Markov chain algorithms for planar lattice structures. SIAM Journal on Computing, 31(1):167-192, 2001. URL: http://dx.doi.org/10.1137/S0097539799360355.
  19. I Lyberg, V Korepin, and J Viti. The density profile of the six vertex model with domain wall boundary conditions. Journal of Statistical Mechanics: Theory and Experiment, 2017(5):053103, 2017. URL: http://stacks.iop.org/1742-5468/2017/i=5/a=053103.
  20. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. I. the attractive case. Communications in Mathematical Physics, 161(3):447-486, Apr 1994. URL: http://dx.doi.org/10.1007/BF02101929.
  21. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. II. the general case. Communications in Mathematical Physics, 161(3):487-514, Apr 1994. URL: http://dx.doi.org/10.1007/BF02101930.
  22. M. Mihail and P. Winkler. On the number of Eulerian orientations of a graph. Algorithmica, 16(4):402-414, Oct 1996. URL: http://dx.doi.org/10.1007/BF01940872.
  23. Linus Pauling. The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. Journal of the American Chemical Society, 57(12):2680-2684, 1935. URL: http://dx.doi.org/10.1021/ja01315a102.
  24. R. Peierls. Statistical theory of adsorption with interaction between the adsorbed atoms. Mathematical Proceedings of the Cambridge Philosophical Society, 32(3):471-476, 1936. URL: http://dx.doi.org/10.1017/S0305004100019162.
  25. Aneesur Rahman and Frank H. Stillinger. Proton distribution in ice and the Kirkwood correlation factor. The Journal of Chemical Physics, 57(9):4009-4017, 1972. URL: http://dx.doi.org/10.1063/1.1678874.
  26. Dana Randall. Slow mixing of Glauber dynamics via topological obstructions. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pages 870-879, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109653.
  27. Dana Randall and Prasad Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41(3):1598-1615, 2000. URL: http://dx.doi.org/10.1063/1.533199.
  28. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, 1989. URL: http://dx.doi.org/10.1016/0890-5401(89)90067-9.
  29. Bill Sutherland. Exact solution of a two-dimensional model for hydrogen-bonded crystals. Phys. Rev. Lett., 19:103-104, Jul 1967. URL: http://dx.doi.org/10.1103/PhysRevLett.19.103.
  30. Olav F. Syljuåsen and M. B. Zvonarev. Directed-loop Monte Carlo simulations of vertex models. Phys. Rev. E, 70:016118, Jul 2004. URL: http://dx.doi.org/10.1103/PhysRevE.70.016118.
  31. A. Yanagawa and J.F. Nagle. Calculations of correlation functions for two-dimensional square ice. Chemical Physics, 43(3):329-339, 1979. URL: http://dx.doi.org/10.1016/0301-0104(79)85201-5.
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 Imprint Privacy Contact