On Computing Total Variation Distance Between Mixtures of Product Distributions

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{T}\mathrm{V}}(\mathbb{P},\mathbb{Q})$ within a multiplicative error of $(1\pm \epsilon )$ in time $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}((nq{)}^{k_1+k_2},1\mathrm{/}\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{p}\mathrm{o}\mathrm{l}\mathrm{y}(n,2^{O(k_1+k_2)})$, and show that exact computation is $\mathrm{\#}\mathsf{P}$-hard when $k_1+k_2=\mathrm{\Theta }(n)$.