Premium
Spatial mixing and nonlocal Markov chains[Note *. *An extended abstract of this paper appeared in the ...]
Author(s) -
Blanca Antonio,
Caputo Pietro,
Sinclair Alistair,
Vigoda Eric
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20844
Subject(s) - markov chain , ising model , spectral gap , mathematics , potts model , statistical physics , markov chain mixing time , mixing (physics) , combinatorics , discrete mathematics , markov property , physics , markov model , mathematical analysis , quantum mechanics , statistics
We consider spin systems with nearest‐neighbor interactions on an n ‐vertex d ‐dimensional cube of the integer lattice graphZ d . 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 (i.e., 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 O ( log n ( log log n ) 2 ) . Our proofs use a variety of techniques for the analysis of Markov chains including coupling, functional analysis and linear algebra.