On Computing Total Variation Distance Between Mixtures of Product Distributions

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 $\mathbb{P}$ and $\mathbb{Q}$ with $k_1$ and $k_2$ product distributions over $[q{]}^n$, respectively, we give a randomized algorithm that approximates $d_{\mathrm{TV}}\left(\mathbb{P},\mathbb{Q}\right)$ within a multiplicative error of $(1\pm \epsilon )$ in time $\mathrm{poly}((nq{)}^{k_1+k_2},1/\epsilon )$. 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 $\mathrm{poly}(n,2^{O(k_1+k_2)})$, and show that exact computation is $\#\mathsf{P}$-hard when $k_1+k_2=\Theta (n)$.