Document Open Access Logo

Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases

Authors Matthew Fahrbach, Dana Randall

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.37.pdf
  • Filesize: 1.25 MB
  • 20 pages

Document Identifiers

Author Details

Matthew Fahrbach
  • School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA
Dana Randall
  • School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

Funding

  • Fahrbach, Matthew: Supported in part by an NSF Graduate Research Fellowship under grant DGE-1650044.
  • Randall, Dana: Supported in part by NSF grants CCF-1637031 and CCF-1733812.

Cite As Get BibTex

Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.37

Abstract

The six-vertex model in statistical physics is a weighted generalization of the ice model on Z^2 (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model represents its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Correlated random walk
  • Markov chain Monte Carlo
  • Six-vertex model

Metrics

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

Related Versions

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. Google Scholar
  2. Prateek Bhakta, Ben Cousins, Matthew Fahrbach, and Dana Randall. Approximately sampling elements with fixed rank in graded posets. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1828-1838. SIAM, 2017. Google Scholar
  3. Pavel Bleher and Vladimir Fokin. Exact solution of the six-vertex model with domain wall boundary conditions. Disordered phase. Communications in Mathematical Physics, 268(1):223-284, 2006. Google Scholar
  4. Pavel Bleher and Karl Liechty. Exact solution of the six-vertex model with domain wall boundary conditions. Ferroelectric phase. Communications in Mathematical Physics, 286(2):777-801, 2009. Google Scholar
  5. Pavel Bleher and Karl Liechty. Exact Solution of the Six-Vertex Model with Domain Wall Boundary Conditions: Antiferroelectric Phase. Communications on Pure and Applied Mathematics, 63(6):779-829, 2010. Google Scholar
  6. N. M. Bogoliubov, A. G. Pronko, and M. B.. Zvonarev. Boundary correlation functions of the six-vertex model. Journal of Physics A: Mathematical and General, 35(27):5525, 2002. Google Scholar
  7. 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. Google Scholar
  8. Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130-141, 2018. Google Scholar
  9. Jin-Yi Cai, Tianyu Liu, and Pinyan Lu. Approximability of the Six-vertex Model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2248-2261. SIAM, 2019. Google Scholar
  10. Sarah Cannon and Dana Randall. Sampling on lattices with free boundary conditions using randomized extensions. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1952-1971. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  11. Henry Cohn, Noam Elkies, and James Propp. Local statistics for random domino tilings of the Aztec diamond. Duke Mathematics Journal, 85(1):117-166, October 1996. URL: https://doi.org/10.1215/S0012-7094-96-08506-3.
  12. David Durfee, Matthew Fahrbach, Yu Gao, and Tao Xiao. Nearly tight bounds for sandpile transience on the grid. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 605-624. SIAM, 2018. Google Scholar
  13. Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.01495.
  14. Patrik L. Ferrari and Herbert Spohn. Domino tilings and the six-vertex model at its free-fermion point. Journal of Physics A: Mathematical and General, 39(33):10297, 2006. Google Scholar
  15. J. Gillis. Correlated random walk. Mathematical Proceedings of the Cambridge Philosophical Society, 51(4):639-651, 1955. Google Scholar
  16. Leslie Ann Goldberg, Russell Martin, and Mike Paterson. Random sampling of 3-colorings in ℤ². Random Structures & Algorithms, 24(3):279-302, 2004. Google Scholar
  17. A. J. Guttmann and A. R. Conway. Square lattice self-avoiding walks and polygons. Annals of Combinatorics, 5(3-4):319-345, 2001. Google Scholar
  18. J. W. Hanneken and D. R. Franceschetti. Exact distribution function for discrete time correlated random walks in one dimension. The Journal of Chemical Physics, 109(16):6533-6539, 1998. Google Scholar
  19. Lingxiao Huang, Pinyan Lu, and Chihao Zhang. Canonical paths for MCMC: From art to science. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 514-527. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  20. Anatoli G Izergin, David A Coker, and Vladimir E Korepin. Determinant formula for the six-vertex model. Journal of Physics A: Mathematical and General, 25(16):4315, 1992. Google Scholar
  21. David Keating and Ananth Sridhar. Random tilings with the GPU. Journal of Mathematical Physics, 59(9):091420, 2018. Google Scholar
  22. Vladimir Korepin and Paul Zinn-Justin. Thermodynamic limit of the six-vertex model with domain wall boundary conditions. Journal of Physics A: Mathematical and General, 33(40):7053, 2000. Google Scholar
  23. Greg Kuperberg. Another proof of the alternative-sign matrix conjecture. International Mathematics Research Notices, 1996(3):139-150, 1996. Google Scholar
  24. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times, volume 107. American Mathematical Society, 2017. Google Scholar
  25. Elliott H Lieb. Exact solution of the problem of the entropy of two-dimensional ice. Physical Review Letters, 18(17):692, 1967. Google Scholar
  26. Elliott H Lieb. Exact Solution of the Two-Dimensional Slater KDP Model of a Ferroelectric. Physical Review Letters, 19(3):108, 1967. Google Scholar
  27. Elliott H Lieb. Residual Entropy of Square Ice. Physical Review, 162(1):162, 1967. Google Scholar
  28. Tianyu Liu. Torpid Mixing of Markov Chains for the Six-vertex Model on ℤ². In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  29. Michael Luby, Dana Randall, and Alistair Sinclair. Markov chain algorithms for planar lattice structures. SIAM Journal on Computing, 31(1):167-192, 2001. Google Scholar
  30. Ivar Lyberg, Vladimir Korepin, G. A. P. Ribeiro, and Jacopo Viti. Phase separation in the six-vertex model with a variety of boundary conditions. Journal of Mathematical Physics, 59(5):053301, 2018. Google Scholar
  31. Ivar Lyberg, Vladimir Korepin, and Jacopo 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. Google Scholar
  32. Colin McQuillan. Approximating holant problems by winding. arXiv preprint, 2013. URL: http://arxiv.org/abs/1301.2880.
  33. 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. Google Scholar
  34. Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probability, 28(2):488-519, 2015. Google Scholar
  35. Dana Randall. Slow mixing of Glauber dynamics via topological obstructions. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 870-879. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  36. Dana Randall and Prasad Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41(3):1598-1615, 2000. Google Scholar
  37. Eric Renshaw and Robin Henderson. The correlated random walk. Journal of Applied Probability, 18(2):403-414, 1981. Google Scholar
  38. Bill Sutherland. Exact solution of a two-dimensional model for hydrogen-bonded crystals. Physical Review Letters, 19(3):103, 1967. Google Scholar
  39. David Bruce Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. The Annals of Applied Probability, 14(1):274-325, 2004. Google Scholar
  40. C. P. Yang. Exact solution of a model of two-dimensional ferroelectrics in an arbitrary external electric field. Physical Review Letters, 19(10):586, 1967. Google Scholar
  41. Doron Zeilberger. Proof of the alternating sign matrix conjecture. Electronic Journal of Combinatorics, 3(2):R13, 1996. Google Scholar
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