Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali
Abstract
For d ≥ 2 and all q≥ q 0(d) we give an efficient algorithm to approximately sample from the q-state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This 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.
Topics & Concepts
Potts modelGlauberMarkov chainInverse temperatureTorusStatistical physicsPartition (number theory)Sampling (signal processing)AlgorithmMathematicsComputer scienceCombinatoricsIsing modelPhysicsStatisticsGeometryFilter (signal processing)ScatteringOpticsComputer visionThermodynamicsMarkov Chains and Monte Carlo MethodsTheoretical and Computational PhysicsStochastic processes and statistical mechanics