Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts\n Transition Point

2010/11/12 by Christian Borgs, Jennifer Chayes, Borgs, Christian +3 · 1 citation
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.1011.3058

Abstract

We study two widely used algorithms for the Potts model on rectangular\nsubsets of the hypercubic lattice Z^d - heat bath dynamics and the\nSwendsen-Wang algorithm - and prove that, under certain circumstances, the\nmixing in these algorithms is torpid or slow. In particular, we show that for\nheat bath dynamics throughout the region of phase coexistence, and for the\nSwendsen-Wang algorithm at the transition point, the mixing time in a box of\nside length L with periodic boundary conditions has upper and lower bounds\nwhich are exponential in L^d-1. This work provides the first upper bound of\nthis form for the Swendsen-Wang algorithm, and gives lower bounds for both\nalgorithms which significantly improve the previous lower bounds that were\nexponential in L/(log L)².\n

Cited by

• Code Swendsen-Wang Dynamics

Related

• Cutoff for the Swendsen-Wang dynamics on the lattice
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Entropy decay in the Swendsen-Wang dynamics on \mathbb Z^d
• The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
• Mixing times of critical 2D Potts models