Entropy decay in the Swendsen-Wang dynamics on ℤd

We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Po s models on the integer la ice Z d . is 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 Z d is O(log n), and we prove this is tight by establishing a matching lower bound on the mixing time. e previous best known bound was O(n). SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the la ice 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. e 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. is 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.