Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
- 26 July 2022
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 51 (4) , 1280-1295
Abstract
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.
Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/S016694/1)
This publication has 23 references indexed in Scilit:
- Approximating partition functions of the two-state spin systemInformation Processing Letters, 2011
- Counting independent sets up to the tree threshold2006
- Strong Spatial Mixing with Fewer Colors for Lattice GraphsSIAM Journal on Computing, 2005
- Mixing in time and space for lattice spin systems: A combinatorial viewRandom Structures & Algorithms, 2004
- Random sampling for the monomer–dimer model on a latticeJournal of Mathematical Physics, 2000
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed GraphJournal of Algorithms, 1998
- For 2-D lattice spin systems weak mixing implies strong mixingCommunications in Mathematical Physics, 1994
- Approximating the PermanentSIAM Journal on Computing, 1989
- Hard-square lattice gasJournal of Statistical Physics, 1980
- Time-Dependent Statistics of the Ising ModelJournal of Mathematical Physics, 1963