Random Structures & Algorithms

Spatial mixing and nonlocal Markov chains

Early View

We consider spin systems with nearest‐neighbor interactions on an n‐vertex d‐dimensional cube of the integer lattice graph . We study the effects that the strong spatial mixing condition (SSM) has on the rate of convergence to equilibrium of nonlocal Markov chains. We prove that when SSM holds, the relaxation time (ie, the inverse spectral gap) of general block dynamics is O(r), where r is the number of blocks. As a second application of our technology, it is established that SSM implies an O(1) bound for the relaxation time of the Swendsen‐Wang dynamics for the ferromagnetic Ising and Potts models. We also prove that for monotone spin systems SSM implies that the mixing time of systematic scan dynamics is . Our proofs use a variety of techniques for the analysis of Markov chains including coupling, functional analysis and linear algebra.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.