mlsanityData to 14 Oct 2026

On Computing Total Variation Distance Between Mixtures of Product Distributions

arXiv 2605.03839 ↗First posted 5 May 2026cs.DS cs.LG math.PRcited by 0

Not on the map. Why?

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).

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

18 of 21 references.

References · 18

  1. 2014Testing probability distributions underlying aggregated datacited by 15
  2. 2018Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applicationscited by 15
  3. 2020Efficient Distance Approximation for Structured High-Dimensional Distributions via Learningcited by 14
  4. 2022On Approximating Total Variation Distancecited by 14
  5. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  6. 2020Source Identification for Mixtures of Product Distributionscited by 11
  7. 2018On Computing the Total Variation Distance of Hidden Markov Modelscited by 8
  8. 2022A simple polynomial-time approximation algorithm for the total variation distance between two product distributionscited by 8
  9. 2023Lifting uniform learners via distributional decompositioncited by 8
  10. 2013Learning Mixtures of Discrete Product Distributions using Spectral Decompositionscited by 7
  11. 2023On Deterministically Approximating Total Variation Distancecited by 7
  12. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
6 more
  1. 2023Total Variation Distance Meets Probabilistic Inferencecited by 5
  2. 2014On the Total Variation Distance of Labelled Markov Chainscited by 4
  3. 2023Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexitycited by 4
  4. 2024Computational Explorations of Total Variation Distancecited by 3
  5. 2025A Distributional-Lifting Theorem for PAC Learningcited by 3
  6. 2025Approximating the total variation distance between spin systemscited by 2

Built on by

Not cited yet.