Paper Info
Title
Mixing in time and space for lattice spin systems: A combinatorial view
Abstract
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., 2004Supported by EPSRC grant “Sharper Analysis of Randomised Algorithms: a Computational Approach” and by EC IST Project RAND-APX.Supported in part by NSF grants CCR-9820951 and CCR-0121555, and by DARPA Cooperative Agreement F30602-00-2-060.
Year
DOI
Venue
2004
10.1002/rsa.v24:4
Random Struct. Algorithms
Keywords
Field
DocType
combinatorial view,lattice spin systems,exponential decay,nearest neighbor,markov chain monte carlo,equilibrium state,functional analysis,mixing time
Discrete mathematics,Glauber,Spin-½,Combinatorics,Exponential decay,Equivalence (measure theory),Integer lattice,Time complexity,Converse implication,Mathematics,Monotone polygon
Journal
Volume
Issue
ISSN
24
4
1042-9832
ISBN
Citations 
PageRank 
3-540-44147-6
15
1.89
References 
Authors
3
4
Name
Order
Citations
PageRank
Martin Dyer1102997.62
Alistair Sinclair21506308.40
Eric Vigoda374776.55
Dror Weitz425819.56