高效计算多个独立分布混合体间的差异，算法速度快且精度可控。
On Computing Total Variation Distance Between Mixtures of Product Distributions
- 用随机算法在多项式时间内逼近两类混合分布的总变差距离
- 对布尔子立方体混合物，可精确计算距离，时间复杂度为多项式
- 当混合成分数量达线性规模时，精确计算属于#P难问题，具理论深度
研究在n维离散域上两个独立分布混合体之间的总变差距离近似计算问题。给定两个混合体ℙ和ℚ，分别由k₁和k₂个乘积分布组成，我们提出一个随机算法，在时间poly((nq)^{k₁+k₂},1/ε)内以(1±ε)的乘法误差逼近d_TV(ℙ,ℚ)。针对{0,1}^n上的布尔子立方体混合体这一特例，我们设计了一个确定性算法，可在时间poly(n,2^{O(k₁+k₂)})内精确计算总变差距离，并证明当k₁+k₂=Θ(n)时，精确计算属于#P难问题。
原文摘要 · Abstract (English)
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 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=Θ(n)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。