Efficient sampling and counting algorithms for the Potts model on \mathbb Z^d at all temperatures

DOI10.1145/3357713.3384271arXiv1909.09298MaRDI QIDQ6325665FDOQ6325665

Will Perkins, Prasad Tetali, Tyler Helmuth, Christian Borgs, Jennifer T. Chayes

Publication date: 19 September 2019

Abstract: For $dge2$ and all $qgeq{q}_0(d)$ we give an efficient algorithm to approximately sample from the $q$-state ferromagnetic Potts and random cluster models on finite tori $(mathbbZ/nmathbbZ{)}^d$ for any inverse temperature $$. This shows that the physical phase transition of the Potts model presents no algorithmic barrier to efficient sampling, and stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen--Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models at all temperatures. Our algorithms are based on representing the random cluster model as a contour model using Pirogov--Sinai theory, and then computing an accurate approximation of the logarithm of the partition function by inductively truncating the resulting cluster expansion. The main innovation of our approach is an algorithmic treatment of unstable ground states, which is essential for our algorithms to apply to all inverse temperatures $$. By treating unstable ground states our work gives a general template for converting probabilistic applications of Pirogov-Sinai theory to efficient algorithms.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Efficient sampling and counting algorithms for the Potts model on $\mathbb Z^d$ at all temperatures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325665)