# On Deterministically Approximating Total Variation Distance

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2023.

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

- [Sharp bounds on aggregate expert error](https://mlsanity.com/paper/2407.16642/) (2024)
- [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)
- [Mitigating Model Drift in Developing Economies Using Synthetic Data and Outliers](https://mlsanity.com/paper/2510.09294/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

Total variation distance (TV distance) is an important measure for the difference between two distributions. Recently, there has been progress in approximating the TV distance between product distributions: a deterministic algorithm for a restricted class of product distributions (Bhattacharyya, Gayen, Meel, Myrisiotis, Pavan and Vinodchandran 2023) and a randomized algorithm for general product distributions (Feng, Guo, Jerrum and Wang 2023). We give a deterministic fully polynomial-time approximation algorithm (FPTAS) for the TV distance between product distributions. Given two product distributions mathbbP and mathbbQ over [q]n, our algorithm approximates their TV distance with relative error varepsilon in time Obigl( fracqn2varepsilon log q log fracnvarepsilon DeltaTV(mathbbP,mathbbQ)  bigr). Our algorithm is built around two key concepts: 1) The likelihood ratio as a distribution, which captures sufficient information to compute the TV distance. 2) We introduce a metric between likelihood ratio distributions, called the minimum total variation distance. Our algorithm computes a sparsified likelihood ratio distribution that is close to the original one w.r.t. the new metric. The approximated TV distance can be computed from the sparsified likelihood ratio. Our technique also implies deterministic FPTAS for the TV distance between Markov chains.