Entropy decay in the Swendsen–Wang dynamics on ℤ^d
Entropy decay in the Swendsen–Wang dynamics on ℤ^d
复制标题
∄^d 上的 Swendsen-Wang 动力学中的熵衰减
DOI：
10.1145/3406325.3451095
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Vigoda, Eric
中科院分区：
文献类型：
--
作者：
Blanca, Antonio;Caputo, Pietro;Parisi, Daniel;Sinclair, Alistair;Vigoda, Eric
研究了整数晶格上铁磁Ising和Potts模型的swendsen - wang动力学的混合时间。这种动力学是一种广泛使用的马尔可夫链，由于它是非局部的，也就是说，它在一步中改变了整个构型，因此在很大程度上抵制了尖锐的分析。我们证明了在任意n顶点立方体上，当强空间混合（SSM）成立时，混合时间是紧的，并通过建立一个匹配的下界证明了这一点。之前最著名的边界是o (n)。SSM是一个标准条件，对应于晶格上自旋之间距离的相关指数衰减，并且已知在整个高温（单相）区域保持ind=2维。我们的结果来自于修正的log-Sobolev不等式，它表达了动力学在每一步以恒定速率收缩相对熵的事实。这一事实的证明利用了在自旋和边的联合概率空间中熵的一个新的因式分解，这是Swendsen-Wang动力学的基础，它扩展到一般的有界度的二部图。这种分解导致了几个额外的结果，包括联合空间上许多自然局部和非局部马尔可夫链的混合时间界限，以及标准随机聚类动力学。
We study the mixing time of theSwendsen-Wangdynamics for the ferromagnetic Ising and Potts models on the integer lattice ℤd. This dynamics is a widely used Markov chain that has largely resisted sharp analysis because it isnon-local, i.e., it changes the entire configuration in one step. We prove that, wheneverstrong spatial mixing (SSM)holds, the mixing time on anyn-vertex cube in ℤdisO(logn), and we prove this is tight by establishing a matching lower bound. The previous best known bound wasO(n). SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the lattice and is known to hold ind=2 dimensions throughout the high-temperature (single phase) region. Our result follows from amodified log-Sobolev inequality, which expresses the fact that the dynamics contracts relative entropy at a constant rate at each step. The proof of this fact utilizes a new factorization of the entropy in the joint probability space over spins and edges that underlies the Swendsen-Wang dynamics, which extends to general bipartite graphs of bounded degree. This factorization leads to several additional results, including mixing time bounds for a number of natural local and non-local Markov chains on the joint space, as well as for the standard random-cluster dynamics.