论文标题
在近似总变化距离上
On Approximating Total Variation Distance
论文作者
论文摘要
总变化距离（电视距离）是概率分布之间距离的基本概念。在这项工作中，我们介绍并研究了计算两个产品分布在域上的电视距离的问题，$ \ {0,1 \}^n $。特别是，我们建立以下结果。 1。精确计算两个产品分布的电视距离的问题是$ \＃\ m athsf {p} $ - 完成。这与其他距离措施（例如KL，卡方和Hellinger）形成鲜明对比，这些测度在边际上张开，导致有效的算法。 2。有一个完全多项式的确定性近似方案（FPTA）用于计算两个产品分布的电视距离$ p $和$ q $，其中$ q $是统一分布。该结果扩展到$ Q $具有恒定数量不同边缘的情况。相比之下，我们表明，当$ p $和$ q $是贝叶斯净分布时，他们的电视距离的相对近似为$ \ mathsf {np} $ - 硬。
Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain $\{0,1\}^n$. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms. 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions $P$ and $Q$ where $Q$ is the uniform distribution. This result is extended to the case where $Q$ has a constant number of distinct marginals. In contrast, we show that when $P$ and $Q$ are Bayes net distributions, the relative approximation of their TV distance is $\mathsf{NP}$-hard.
