# Approximating the total variation distance between spin systems

arXiv: https://arxiv.org/abs/2502.05437 · HTML: https://mlsanity.com/paper/2502.05437/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 8 Feb 2025.

## Builds on (most cited first, 17 of 17)

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains](https://mlsanity.com/paper/2203.04163/) (2022)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion](https://mlsanity.com/paper/2011.02075/) (2020)
- [On Computing the Total Variation Distance of Hidden Markov Models](https://mlsanity.com/paper/1804.06170/) (2018)
- [A simple polynomial-time approximation algorithm for the total variation distance between two product distributions](https://mlsanity.com/paper/2208.00740/) (2022)
- [On Deterministically Approximating Total Variation Distance](https://mlsanity.com/paper/2309.14696/) (2023)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [On the Total Variation Distance of Labelled Markov Chains](https://mlsanity.com/paper/1405.2852/) (2014)
- [Rapid Mixing at the Uniqueness Threshold](https://mlsanity.com/paper/2411.03413/) (2024)
- [Computational Explorations of Total Variation Distance](https://mlsanity.com/paper/2412.10370/) (2024)
- [Rapid mixing of Glauber dynamics via spectral independence for all degrees](https://mlsanity.com/paper/2105.15005/) (2021)
- [Optimal mixing for two-state anti-ferromagnetic spin systems](https://mlsanity.com/paper/2203.07771/) (2022)
- [Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields](https://mlsanity.com/paper/2205.01985/) (2022)
- [Sharp bounds on aggregate expert error](https://mlsanity.com/paper/2407.16642/) (2024)

## Built on by (most cited first, 2 of 2)

- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

Spin systems form an important class of undirected graphical models. For two Gibbs distributions μ and nu induced by two spin systems on the same graph G = (V, E), we study the problem of approximating the total variation distance dTV(μ,nu) 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 dTV(μS,nuS) between two marginal distributions on an arbitrary subset S subseteq V. We prove that this problem remains hard even when both μ and nu admit polynomial-time sampling and approximate counting algorithms.