Premium
Mixing in time and space for lattice spin systems: A combinatorial view
Author(s) -
Dyer Martin,
Sinclair Alistair,
Vigoda Eric,
Weitz Dror
Publication year - 2004
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.20004
Subject(s) - glauber , mathematics , mixing (physics) , markov chain , lattice (music) , statistical physics , monotone polygon , combinatorics , mathematical proof , discrete mathematics , exponential function , physics , mathematical analysis , quantum mechanics , statistics , geometry , acoustics , scattering
The paper considers spin systems on the d ‐dimensional integer lattice ℤ d with nearest‐neighbor interactions. A sharp equivalence is proved between decay with distance of spin correlations (a spatial property of the equilibrium state) and rapid mixing of the Glauber dynamics (a temporal property of a Markov chain Monte Carlo algorithm). Specifically, we show that if the mixing time of the Glauber dynamics is O ( n log n ) then spin correlations decay exponentially fast with distance. We also prove the converse implication for monotone systems, and for general systems we prove that exponential decay of correlations implies O ( n log n ) mixing time of a dynamics that updates sufficiently large blocks (rather than single sites). While the above equivalence was already known to hold in various forms, we give proofs that are purely combinatorial and avoid the functional analysis machinery employed in previous proofs. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004