Spatial Mixing and Systematic Scan Markov chains

Abstract

We consider spin systems on the integer lattice graph ${\mathbb{Z}}^d$ with nearest-neighbor interactions. We develop a combinatorial framework for establishing that exponential decay with distance of spin correlations, specifically the strong spatial mixing condition (SSM), implies rapid mixing of a large class of Markov chains. As a first application of our method we prove that SSM implies $O(\log n)$ mixing of systematic scan dynamics (under mild conditions) on an $n$-vertex $d$-dimensional cube of the integer lattice graph ${\mathbb{Z}}^d$. Systematic scan dynamics are widely employed in practice but have proved hard to analyze. A second application of our technology concerns the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models. We show that SSM implies an $O(1)$ bound for the relaxation time (i.e., the inverse spectral gap). As a by-product of this implication we observe that the relaxation time of the Swendsen-Wang dynamics in square boxes of ${\mathbb{Z}}^2$ is $O(1)$ throughout the subcritical regime of the $q$-state Potts model, for all $q\ge 2$. We also use our combinatorial framework to give a simple coupling proof of the classical result that SSM entails optimal mixing time of the Glauber dynamics. Although our results in the paper focus on $d$-dimensional cubes in ${\mathbb{Z}}^d$, they generalize straightforwardly to arbitrary regions of ${\mathbb{Z}}^d$ and to graphs with subexponential growth.

See arXiv:1708.01513 for a corrected version. The new version includes a new proof of the result for the Swendsen-Wang dynamics, as well as new results for block dynamics and for the alternating scan dynamics. Our results for the systematic scan dynamics now require monotonicity of the spin system

References in corpus (4)

• The computational hardness of counting in two-spin models on d-regular graphs
• Systematic scan for sampling colorings
• Swendsen-Wang is faster than single-bond dynamics
• Rapid mixing of Swendsen-Wang and single-bond dynamics in two dimensions