The random-cluster model is a unifying framework for studying random graphs, spin systems and electrical networks that plays a fundamental role in designing efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical ferromagnetic Ising and Potts models. 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, where the underlying graph is the complete graph on $n$ vertices. The random-cluster model is parametrized by an it edge probability $p$ and a cluster weight $q$. Our focus is on the critical regime: $p = p_c(q)$ and $q \in (1,2)$, where $p_c(q)$ is the threshold corresponding to the order-disorder phase transition of the model. We show that the mixing time of the Chayes-Machta dynamics is $O(\log n \cdot \log \log n)$ in this parameter regime, which reveals that the dynamics does not undergo an exponential slowdown at criticality, a surprising fact that had been predicted (but not proved) by statistical physicists. This also provides a nearly optimal bound (up to the $\log\log n$ factor) for the mixing time of the mean-field Chayes-Machta dynamics in the only regime of parameters where no non-trivial bound was previously known. Our proof consists of a multi-phased coupling argument that combines several key ingredients, including a new local limit theorem, a precise bound on the maximum of symmetric random walks with varying step sizes, and tailored estimates for critical random graphs. In addition, we derive an improved comparison inequality between the mixing time of the Chayes-Machta dynamics and that of the local Glauber dynamics on general graphs; this results in better mixing time bounds for the local dynamics in the mean-field setting.
翻译:随机集群模型是一个用于研究随机图形、 旋转系统和电气网络的统一框架。 随机集群模型在设计传统铁磁性Ising 和 Potts 模型的高效 Markov 链子 Monte Carlo (MCMC MC) 取样算法( MCMC ) 方面发挥根本作用。 在本论文中, 我们研究一个自然的非本地 Markov 链子( Chayes- Machta ), 称为 Chayes- Machta 随机集群模型的平均场外情况, 其基本图表是 $$$ 的完整图表。 随机集群模型模型的混合时间是 $O ( log n\ cdolog), 其边缘值是 $ 美元 。 我们的焦点是: $ pp = p_ c (q) $ 和 $ 美元 美元 元元的取样法, 其最接近的精确时间值是 。