Entropy decay in the Swendsen-Wang dynamics
Entropy decay in the Swendsen-Wang dynamics
复制标题
Swendsen-Wang 动力学中的熵衰减
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Eric Vigoda
中科院分区：
文献类型：
--
作者：
Antonio Blanca;P. Caputo;D. Parisi;A. Sinclair;Eric Vigoda
研究了整数晶格上铁磁Ising和Potts模型Swendsen-Wang动力学的混合时间.这种动力学是一种广泛使用的马尔可夫链，它在很大程度上抵制了尖锐的分析，因为它是非局部的，即它在一步内改变了整个构型。证明了当强空间混合(SSM)成立时，${mathbb Z}^d$的任意$n$-顶点立方体上的混合时间为$O(Logn)$，改进了已知的$O(N)$的界.SSM是一个标准条件，对应于关联与晶格上自旋之间的距离的指数衰减，并且已知在整个高温(单相)区域内都适用于$d=2$维。我们的结果来自一个修正的LOG-Soblev不等式，它表示动力学在每一步以恒定的速度收缩相对熵的事实。这一事实的证明利用了自旋和边缘上的联合概率空间中的熵的一种新的因式分解，这是Swendsen-Wang动力学的基础。这种因式分解导致了几个额外的结果，包括联合空间上的一些自然局部和非局部马尔可夫链的混合时间界，以及标准随机簇动力学的混合时间界。
We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models on the integer lattice ${mathbb Z}^d$. This dynamics is a widely used Markov chain that has largely resisted sharp analysis because it is non-local, i.e., it changes the entire configuration in one step. We prove that, whenever strong spatial mixing (SSM) holds, the mixing time on any $n$-vertex cube of ${mathbb Z}^d$ is $O(log n)$, improving on the previous best known bound of $O(n)$. SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the lattice and is known to hold in $d=2$ dimensions throughout the high-temperature (single phase) region. Our result follows from a modified 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. 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.