论文标题
树木上的Swendsen-Wang动力学
The Swendsen-Wang Dynamics on Trees
论文作者
论文摘要
Swendsen-Wang算法是一种精致的，广泛使用的马尔可夫链，用于从Gibbs分布中为铁磁性ISING和POTTS模型进行采样。事实证明，这条连锁店很难分析，部分原因是其更新的全球性质。我们介绍了完整$ d $ -ary树的Swendsen-Wang算法的收敛速率的最佳界限。我们的边界扩展到非唯一性区域，并应用于所有边界条件。 我们表明，Martinelli等人的局部马尔可夫链研究中引入了称为方差混合和熵混合的空间混合条件。 （2003年），暗示$ω（1）$频谱差距和$ o（\ log {n}）$混合时间，用于$ d $ -ary树上的Swendsen-Wang Dynamics。我们还表明，这些边界在渐近上是最佳的。结果，我们为整个树独特性区域的所有边界条件的Swendsen-Wang动力学建立了$θ（\ log {n}）$混合；实际上，我们的界限超出了Ising模型的唯一阈值，对于$ Q $ $ Q $，相对于$ d $，$ q $ - 州Potts模型。我们的证明具有差异混合条件的新频谱视图，灵感来自于高维扩张器上的几种快速混合结果，并利用了在空间混合条件下熵的块分解的最新研究。
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to the global nature of its updates. We present optimal bounds on the convergence rate of the Swendsen-Wang algorithm for the complete $d$-ary tree. Our bounds extend to the non-uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as Variance Mixing and Entropy Mixing, introduced in the study of local Markov chains by Martinelli et al. (2003), imply $Ω(1)$ spectral gap and $O(\log{n})$ mixing time, respectively, for the Swendsen-Wang dynamics on the $d$-ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish $Θ(\log{n})$ mixing for the Swendsen-Wang dynamics for all boundary conditions throughout the tree uniqueness region; in fact, our bounds hold beyond the uniqueness threshold for the Ising model, and for the $q$-state Potts model when $q$ is small with respect to $d$. Our proofs feature a novel spectral view of the Variance Mixing condition inspired by several recent rapid mixing results on high-dimensional expanders and utilize recent work on block factorization of entropy under spatial mixing conditions.
