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

• 成果类型: Article
• 署名作者: Borgs, Christian; Chayes, Jennifer T.; Tetali, Prasad
• 署名单位: University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; Microsoft
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-010-0329-0
• 发表日期: 2012
• 页码: 509-557
• 关键词: phase-diagrams; DYNAMICS; systems; MODEL

摘要

We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice Z(d)-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 Ld-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).