Dynamics for the Mean-field Random-cluster Model
Dynamics for the Mean-field Random-cluster Model
复制标题
平均场随机簇模型的动力学
DOI：
10.4230/lipics.approx-random.2015.528
复制
发表时间：
2014
影响因子：
1.6
通讯作者：
A. Sinclair
中科院分区：
文献类型：
--
作者：
Antonio Blanca;A. Sinclair
随机聚类模型是研究随机图、物理自旋系统和随机生成树的统一框架。这个模型与伊辛和波茨的经典模型密切相关，尽管它比伊辛和波茨的模型更普遍，但人们对其动力学的理解却少得多。本文研究了随机聚类模型平均场情况下的自然非局部马尔可夫链Chayes-Machta动力学，并确定了模型参数$\lambda$的临界状态$(\lambda_s,\lambda_S)$，该状态下动力学经历指数级减速。即，我们证明，当$\lambda \not\in [\lambda_s,\lambda_S]$时，混合时间为$\Theta(\log n)$，当$\lambda \in (\lambda_s,\lambda_S)$时，混合时间为$\exp(\Omega(\sqrt{n}))$。这些结果适用于第二个模型参数$q > 1$的所有值。因此，除了已经很好理解的特殊情况$q=2$（对应于Ising模型）之外，我们获得了关于$\lambda$几乎全范围值的$q$值的随机聚类模型的第一次动态分析。此外，我们证明了局部热浴动力学经历了类似的指数放缓$(\lambda_s,\lambda_S)$。
The random-cluster model is a unifying framework for studying random graphs, spin systems in physics and random spanning trees. The model is closely related to, though much more general than the classical Ising and Potts models, but its dynamics are much less well understood. In this paper we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, and identify a critical regime $(\lambda_s,\lambda_S)$ of the model parameter $\lambda$ in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is $\Theta(\log n)$ if $\lambda \not\in [\lambda_s,\lambda_S]$, and $\exp(\Omega(\sqrt{n}))$ when $\lambda \in (\lambda_s,\lambda_S)$. These results hold for all values of the second model parameter $q > 1$. Thus, we obtain the first analysis of a dynamics for the random-cluster model for values of $q$ other than the already well understood special case $q=2$ (which corresponds to the Ising model) over almost the full range of values of $\lambda$. In addition, we prove that the local heat-bath dynamics undergoes a similar exponential slowdown in $(\lambda_s,\lambda_S)$.
Swendsen-Wang 比单键动力学更快
DOI：
10.1137/120864003
发表时间：
2014
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
M. Ullrich
通讯作者：
M. Ullrich