Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point

We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice —heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynami...

Full description

Saved in:
Bibliographic Details
Published in:Probability theory and related fields 2012-04, Vol.152 (3-4), p.509-557
Main Authors: Borgs, Christian, Chayes, Jennifer T., Tetali, Prasad
Format: Article
Language:English
Subjects:
Algorithms
Boundary conditions
Computer science
Dynamic tests
Dynamics
Economics
Equilibrium
Finance
Heat
Insurance
Lattices
Lower bounds
Management
Markov analysis
Mathematical analysis
Mathematical and Computational Biology
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Phase transitions
Probability
Probability theory
Probability Theory and Stochastic Processes
Quantitative Finance
Statistical physics
Statistics for Business
Studies
Temperature
Theoretical
Topological manifolds
Transition points
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice —heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L d -1 . This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L /(log L ) 2 .
ISSN:0178-8051
1432-2064
DOI:10.1007/s00440-010-0329-0