提出新方法估算自旋系统间距离，可高效计算不同模型差异。
Approximating the total variation distance between spin systems
- 将总变差距离估算转化为采样与计数问题
- 在唯一性区域等场景下实现ε相对误差逼近
- 适用于硬核模型、铁磁/反铁磁伊辛模型等
自旋系统是一类重要的无向图模型。针对同一图 $G = (V, E)$ 上两个吉布斯分布 $μ$ 与 $ν$，本文研究以 $ε$-相对误差近似总变差距离 $d_{TV}(μ,ν)$ 的问题。提出一种新归约方法，将该距离估算与采样及近似计数关联。应用包括硬核模型、反铁磁伊辛模型在唯一性区域、铁磁伊辛模型以及满足谱条件的广义伊辛模型。此外，我们还探讨了在任意子集 $S \&subseteq V$ 上两个边缘分布 $μ_S$ 与 $ν_S$ 之间 $d_{TV}(μ_S,ν_S)$ 的近似复杂度。证明即使 $μ$ 与 $ν$ 均具备多项式时间采样与近似计数算法，该问题仍保持计算困难。
原文摘要 · Abstract (English)
Spin systems form an important class of undirected graphical models. For two Gibbs distributions $μ$ and $ν$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{TV}(μ,ν)$ with an $ε$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{TV}(μ_S,ν_S)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $μ$ and $ν$ admit polynomial-time sampling and approximate counting algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。