On Computing Total Variation Distance Between Mixtures of Product Distributions

arXiv:2605.03839v1 Announce Type: cross Abstract: 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 P and Q with k_1 and k_2 product distributions over [q]^n, respectively, we give a randomized algorithm that approximates d_{TV}left({P},{Q}right) within a multiplicative error of (1pm arepsilon) in time poly((nq)^{k_1+k_2},1/arepsilon). We also study the special case of mixtures of Boolean subcubes over {0,1}^n. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time poly(n,2^{O(k_1+k_2)}), and show that exact computation is #mathsf{P}-hard when k_1+k_2=Theta(n).

Source: arXiv cs.LG | 2026-05-06