Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point
Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point
复制标题
Swendsen-Wang 算法在 Potts 转变点处混合的严格界限
DOI：
10.1007/s00440-010-0329-0
复制
发表时间：
2010
影响因子：
2
通讯作者：
P. Tetali
中科院分区：
文献类型：
--
作者：
C. Borgs;J. Chayes;P. Tetali
我们研究了超立方晶格$${\mathbb{Z}^{d}}$$矩形子集上Potts模型的两种广泛使用的算法——热浴动力学和swenden - wang算法，并证明在某些情况下，这些算法中的混合是迟钝的或缓慢的。特别地，我们证明了对于整个相共存区域的热浴动力学，以及对于过渡点的Swendsen-Wang算法，具有周期边界条件的边长为L的盒中的混合时间在Ld-1中具有指数上界和下界。这项工作为Swendsen-Wang算法提供了这种形式的第一个上界，并给出了两种算法的下界，这两种算法显著改进了之前的L/(log L)2指数下界。
We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice $${\mathbb{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.