The Swendsen–Wang dynamics on trees

The Swendsen–Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to its global nature. We present optimal bounds on the convergence rate of the Swendsen–Wang algorithm for the complete (Formula presented.) -ary tree. Our bounds extend to the non-uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as variance mixing and entropy mixing imply (Formula presented.) spectral gap and (Formula presented.) mixing time, respectively, for the Swendsen–Wang dynamics on the (Formula presented.) -ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish (Formula presented.) mixing for the Swendsen–Wang dynamics for all boundary conditions throughout (and beyond) the tree uniqueness region. Our proofs feature a novel spectral view of the variance mixing condition and utilize recent work on block factorization of entropy.