Spatial Mixing and Systematic Scan Markov chains

MaRDI QIDQ6280507zbMATH OpenFDO

Authors Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda

Publication date 5 December 2016

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(logn)$ 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 $qge2$. 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.

This page was built for publication: Spatial Mixing and Systematic Scan Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280507)