2020/07/14 by Antonio Blanca, Pietro Caputo, Blanca, Antonio +7 · 3 citations
Mathematics · Physics and Astronomy · #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2007.06931
openalex publication_date 2020/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models on the integer lattice \mathbb Zd. 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 in \mathbb Zd is O(log n), and we prove this is tight by establishing a matching lower bound on the mixing time. The previous best known bound was 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, 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.