Perfect sampling of Ising spin glasses with bounding chains
Abstract
We study perfect sampling algorithms for Ising spin glasses based on coupling from the past and bounding chains, on several graph families and coupling distributions. For the single-site bounding chain, we establish coalescence in O(nlog n) updates under Dobrushin conditions. On sparse random graphs, our numerical results suggest that efficient sampling extends throughout the tree-uniqueness regime, with a slowdown beyond this threshold. On Erdős-Rényi random graphs 𝒢(n,d/n) with standard Gaussian couplings, we introduce a block bounding chain and prove its coalescence in O(nlog n) block updates in the tree-uniqueness regime for sufficiently large d, each block update requiring O(n) operations, adapting a proof in~\cite{Efthymiou_Zampetakis_2024} for the rapid mixing of block Glauber dynamics. On periodic lattices, our experiments instead suggest that the single-site bounding chain is limited by the looseness of its bounding envelope, whereas on the Sherrington-Kirkpatrick model, slow coalescence is accompanied by damage spreading at every inverse temperature tested. These observations motivate alternative bounding representations and couplings as strategies to improve perfect sampling on spin glasses.
Related
- Free energy of non-convex multi-species spin glasses with centered Ising spins
- Free energy of non-convex multi-species Ising spin glasses with external fields
- A Simple Approach to the Complexity of Mean Field Ising Spin Glasses
- TAP states at upper deviations of the free energy: existence, localization and marginal stability in Ising spin glasses
- Signed FK percolation in Ising spin glasses
BibTeX
@misc{peron2026perfect,
title = {{Perfect sampling of Ising spin glasses with bounding chains}},
author = {Lukas Péron and Louise Budzynski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37300},
eprint = {2610.37300},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37300},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Perfect sampling of Ising spin glasses with bounding chains
AU - Lukas Péron
AU - Louise Budzynski
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37300
UR - https://arxiv.org/abs/2610.37300
AB - We study perfect sampling algorithms for Ising spin glasses based on coupling from the past and bounding chains, on several graph families and coupling distributions. For the single-site bounding chain, we establish coalescence in O(nlog n) updates under Dobrushin conditions. On sparse random graphs, our numerical results suggest that efficient sampling extends throughout the tree-uniqueness regime, with a slowdown beyond this threshold. On Erdős-Rényi random graphs 𝒢(n,d/n) with standard Gaussian couplings, we introduce a block bounding chain and prove its coalescence in O(nlog n) block updates in the tree-uniqueness regime for sufficiently large d, each block update requiring O(n) operations, adapting a proof in~\cite{Efthymiou_Zampetakis_2024} for the rapid mixing of block Glauber dynamics. On periodic lattices, our experiments instead suggest that the single-site bounding chain is limited by the looseness of its bounding envelope, whereas on the Sherrington-Kirkpatrick model, slow coalescence is accompanied by damage spreading at every inverse temperature tested. These observations motivate alternative bounding representations and couplings as strategies to improve perfect sampling on spin glasses.
ER -