{"id":"arxiv/2605.03839","url":"https://arxiv.org/abs/2605.03839","tags":["cs.DS","cs.LG","math.PR"],"score":0,"title":"On Computing Total Variation Distance Between Mixtures of Product Distributions","domain":"cs.DS","source":"arxiv","authors":["Weiming Feng","Yucheng Fu","Minji Yang","Anqi Zhang"],"reviews":0,"subject":"cs.DS","summary":"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 \\varepsilon)$ in time $\\mathrm{poly}((nq)^{k_1+k_2},1/\\varepsilon)$. We also study the special case of mixtures of Boolean subcubes over $\\{0,1\\}^n$. For this class, we give a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-05","reactions":{}}