Deterministic approximation of differences between spin system models
Deterministic Approximation of the Total Variation Distance Between Spin Systems
Data Structures and Algorithms
Summary
This paper looks at how to accurately compare two complex random models called spin systems that are used to study things like magnets or networks. The authors focus on measuring how different two versions of these models are by approximating a key metric called total variation distance, without relying on randomness in their calculations. They provide efficient algorithms for certain types of models, including the hard-core and Ising models, that work under specific conditions related to the system's parameters. Their approach transforms the problem into computing something called partition functions, which are easier to estimate deterministically.
What this means in practice
- •For statistical physics modelers: Estimate differences between physical spin system models accurately and efficiently for bounded-degree graph representations.
- •For network reliability engineers: Provide deterministic bounds on distribution differences in network models to improve robustness assessments where randomness is impractical.
Authors
Zelin Li, Minji Yang
Abstract
We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.