The Swendsen-Wang process does not always mix rapidly
The Swendsen-Wang process does not always mix rapidly
复制标题
Swendsen-Wang 过程并不总是快速混合
DOI：
10.1145/258533.258662
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Jerrum
中科院分区：
文献类型：
--
作者：
Vivek Gore;M. Jerrum
Swendsen-Wang 过程为 q 态 Potts 模型提供了一种可能的动力学。此过程的计算机模拟广泛用于估计均衡（或吉布斯）分布中波茨系统的各种可观测值（随机变量）的期望。这种模拟的合法性取决于过程达到平衡的收敛速度，以“混合时间”来衡量。经验观察表明，在许多具有实际意义的情况下，斯文森-王过程的混合时间很短，尽管这种理想行为的证据仅在一些非常特殊的情况下才为人所知。尽管如此，我们表明，有时 Swendsen-Wang 过程的混合时间与系统的大小成指数关系。这种不良行为与 q > 2 态 Potts 系统中的一阶相变现象有关。
The Swendsen–Wang process provides one possible dynamics for the q-state Potts model. Computer simulations of this process are widely used to estimate the expectations of various observables (random variables) of a Potts system in the equilibrium (or Gibbs) distribution. The legitimacy of such simulations depends on the rate of convergence of the process to equilibrium, as measured by the “mixing time.” Empirical observations suggest that the mixing time of the Swendsen–Wang process is short in many instances of practical interest, although proofs of this desirable behavior are known only for some very special cases. Nevertheless, we show that there are occasions when the mixing time of the Swendsen–Wang process is exponential in the size of the system. This undesirable behavior is related to the phenomenon of first-order phase transitions in Potts systems with q > 2 states.