We consider spin systems with nearest-neighbor interactions on an n-vertex d-dimensional cube of the integer lattice graph Zd. We study the effects that exponential decay with distance of spin correlations, specifically the strong spatial mixing condition (SSM), has on the rate of convergence to equilibrium of non-local Markov chains. We prove that SSM implies O(log n) mixing of a block dynamics whose steps can be implemented efficiently. We then develop a methodology, consisting of several new comparison inequalities concerning various block dynamics, that allow us to extend this result to other non-local dynamics. As a first application of our method we prove that, if SSM holds, then the relaxation time (i.e., the inverse spectral gap) of general block dynamics is O(r), where r is the number of blocks. 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. As a by-product of this implication we observe that the relaxation time of the Swendsen-Wang dynamics in square boxes of Z2 is O(1) throughout the subcritical regime of the q-state Potts model, for all q ≥ 2. 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). Systematic scan dynamics are widely employed in practice but have proved hard to analyze. Our proofs use a variety of techniques for the analysis of Markov chains including coupling, functional analysis and linear algebra.
Blanca, A., Caputo, P., Sinclair, A.J., Vigoda, E. (2018). Spatial mixing and non-local Markov chains. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1965-1980). Association for Computing Machinery [10.1137/1.9781611975031.128].
Spatial mixing and non-local Markov chains
Caputo, Pietro;SINCLAIR, Alistair John;
2018-01-01
Abstract
We consider spin systems with nearest-neighbor interactions on an n-vertex d-dimensional cube of the integer lattice graph Zd. We study the effects that exponential decay with distance of spin correlations, specifically the strong spatial mixing condition (SSM), has on the rate of convergence to equilibrium of non-local Markov chains. We prove that SSM implies O(log n) mixing of a block dynamics whose steps can be implemented efficiently. We then develop a methodology, consisting of several new comparison inequalities concerning various block dynamics, that allow us to extend this result to other non-local dynamics. As a first application of our method we prove that, if SSM holds, then the relaxation time (i.e., the inverse spectral gap) of general block dynamics is O(r), where r is the number of blocks. 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. As a by-product of this implication we observe that the relaxation time of the Swendsen-Wang dynamics in square boxes of Z2 is O(1) throughout the subcritical regime of the q-state Potts model, for all q ≥ 2. 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). Systematic scan dynamics are widely employed in practice but have proved hard to analyze. Our proofs use a variety of techniques for the analysis of Markov chains including coupling, functional analysis and linear algebra.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
