# On Computing Total Variation Distance Between Mixtures of Product Distributions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 21 references that are in the map.
- First posted on arXiv 5 May 2026.

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

- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [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)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [Source Identification for Mixtures of Product Distributions](https://mlsanity.com/paper/2012.14540/) (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)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Learning Mixtures of Discrete Product Distributions using Spectral Decompositions](https://mlsanity.com/paper/1311.2972/) (2013)
- [On Deterministically Approximating Total Variation Distance](https://mlsanity.com/paper/2309.14696/) (2023)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [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)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [Computational Explorations of Total Variation Distance](https://mlsanity.com/paper/2412.10370/) (2024)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)

## Abstract (arXiv)

We study the problem of approximating the total variation distance between two mixtures of product distributions over an n-dimensional discrete domain. Given two mixtures mathbbP and mathbbQ with k1 and k2 product distributions over [q]n, respectively, we give a randomized algorithm that approximates dTVleft(mathbbP,mathbbQright) within a multiplicative error of (1± varepsilon) in time poly((nq)k1+k2,1/varepsilon). We also study the special case of mixtures of Boolean subcubes over 0,1n. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time poly(n,2O(k1+k2)), and show that exact computation is #mathsfP-hard when k1+k2=Theta(n).