# Total Variation Distance Meets Probabilistic Inference

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 17 Sep 2023.

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

- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [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)
- [A simple polynomial-time approximation algorithm for the total variation distance between two product distributions](https://mlsanity.com/paper/2208.00740/) (2022)
- [Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach](https://mlsanity.com/paper/2305.17058/) (2023)
- [Scaling Exact Inference for Discrete Probabilistic Programs](https://mlsanity.com/paper/2005.09089/) (2020)
- [Exact Bayesian Inference for Loopy Probabilistic Programs using Generating Functions](https://mlsanity.com/paper/2307.07314/) (2023)

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

- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [Approximating the Total Variation Distance between Gaussians](https://mlsanity.com/paper/2503.11099/) (2025)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)
- [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)

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between same-structure distributions over any class of Bayes nets for which there is an efficient probabilistic inference algorithm. In particular, it leads to an FPRAS for estimating TV distances between distributions that are defined over a common Bayes net of small treewidth. Prior to this work, such approximation schemes only existed for estimating TV distances between product distributions. Our approach employs a new notion of partial couplings of high-dimensional distributions, which might be of independent interest.