Projects per year
Abstract
We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with sub-exponential neighborhood growth like Z𝑑, our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer-dimer models in such graphs.
Original language | English |
---|---|
Pages (from-to) | 678-709 |
Number of pages | 32 |
Journal | Random Structures and Algorithms |
Volume | 61 |
Issue number | 4 |
Early online date | 18 Feb 2022 |
DOIs | |
Publication status | Published - 1 Dec 2022 |
Keywords / Materials (for Non-textual outputs)
- perfect sampling
- Gibbs distribution
- spatial mixing
Fingerprint
Dive into the research topics of 'Perfect sampling from spatial mixing'. Together they form a unique fingerprint.Projects
- 1 Active
-
New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
1/01/21 → 31/12/25
Project: Research