On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
复制标题
DOI：
10.1137/1.9781611977073.145
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Antonio Blanca;P. Caputo;Zongchen Chen;D. Parisi;Daniel Stefankovic;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Antonio Blanca;P. Caputo;Zongchen Chen;D. Parisi;Daniel Stefankovic;Eric Vigoda
对于一般的自旋系统，我们证明了任何局部马尔可夫链的压缩耦合意味着混合时间和修改后的log-Sobolev常数的一个大类的马尔可夫链，包括Glauber动力学，任意热浴块动力学，和Swendsen-Wang动力学的最佳界限。这揭示了一个新的概率技术之间的联系，用于约束收敛到平稳性和分析工具，用于分析相对熵的衰减。作为我们一般结果的推论，我们得到了当q>（11/6 -\epsilon_0）\Delta $时n$-顶点图的随机q$-染色的Glauber动力学的混合时间为O（n\log{n}）$，混合时间为O（n\log {n}）$，混合时间为O（n\log {n}）$，混合时间为O\Omega（1/n）$.当系统的参数位于树唯一性区域时，我们还得到了铁磁Ising模型在最大度为常数的n$-顶点图上的Swendsen-Wang动力学的O（\log{n}）$混合时间和$\Omega（1）$修正的log-Sobolev常数.在我们的研究结果的核心是新的技术，建立光谱独立的自旋系统和块因式分解的相对熵。一方面，我们证明了一个压缩耦合的局部马尔可夫链意味着谱独立的吉布斯分布。另一方面，我们表明，频谱独立意味着因式分解的熵为任意块，建立相应的块动态的修改后的对数Sobolev常数的最佳界限。
For general spin systems, we prove that a contractive coupling for any local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heat-bath block dynamics, and the Swendsen-Wang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain $O(n\log{n})$ mixing time and $\Omega(1/n)$ modified log-Sobolev constant of the Glauber dynamics for sampling random $q$-colorings of an $n$-vertex graph with constant maximum degree $\Delta$ when $q>(11/6 - \epsilon_0)\Delta$ for some fixed $\epsilon_0>0$. We also obtain $O(\log{n})$ mixing time and $\Omega(1)$ modified log-Sobolev constant of the Swendsen-Wang dynamics for the ferromagnetic Ising model on an $n$-vertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of a local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified log-Sobolev constant of the corresponding block dynamics.