← 研踪 PaperTrailarXiv:2611.04786 · v1
Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold
首次提交 2026-11-03 20:25
版本更新 2026-11-03 20:25
雷达观测 2026-11-04 23:39
摘要
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $Δ$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $Δ\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $β=Δ/(Δ-2)$. 2.Almost-linear XY sampling. For $Δ\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $Δ$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $β-1\le 0.1(β_{\mathrm{od}}(q,Δ)-1)$, where $β_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 20:25 · 最新观测版本
Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $Δ$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $Δ\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $β=Δ/(Δ-2)$. 2.Almost-linear XY sampling. For $Δ\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $Δ$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $β-1\le 0.1(β_{\mathrm{od}}(q,Δ)-1)$, where $β_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.
查看此版本解读 →查看此版本原文 ↗