标题： 使用条件样本测试概率分布 显示英文标题

标题： Testing probability distributions using conditional samples

摘要： 我们研究了一种新的概率分布属性测试框架，通过考虑具有条件采样Oracle的分布测试算法。 * 这是一个Oracle，它以未知概率分布 $\D$ 的域 $[N]$ 的子集 $S \subseteq [N]$ 作为输入，并返回从限制在 $S$ 上的条件概率分布 $\D$ 中抽取的样本。 这种新模型在设计分布测试算法方面提供了极大的灵活性；特别是，此模型中的测试算法可以是自适应的。 我们在这一新框架及其某些变体中研究了一系列自然的分布测试问题，并给出了查询复杂度的上下界。 这些问题包括测试$\D$是否为均匀分布$\calU$；测试$\D = \D^\ast$对于显式提供的$\D^\ast$；测试两个未知分布$\D_1$和$\D_2$是否等价；以及估计$\D$与均匀分布之间的变分距离。 在高层次上，我们的主要发现是，我们考虑的新“条件采样”框架是一个强有力的框架：虽然上述所有问题在标准模型中的样本复杂度为$\Omega(\sqrt{N})$（在某些情况下，复杂度必须几乎线性于$N$），我们在条件采样设置中为所有这些问题给出了$\poly(\log N, 1/\eps)$-查询算法（在某些情况下为与$N$无关的$\poly(1/\eps)$-查询算法）。*独立于我们的工作，Chakraborty 等人也考虑了这个框架。我们在子节 [1.4] 中讨论了他们的工作。 显示英文摘要

摘要： We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle.* This is an oracle that takes as input a subset $S \subseteq [N]$ of the domain $[N]$ of the unknown probability distribution $\D$ and returns a draw from the conditional probability distribution $\D$ restricted to $S$. This new model allows considerable flexibility in the design of distribution testing algorithms; in particular, testing algorithms in this model can be adaptive. We study a wide range of natural distribution testing problems in this new framework and some of its variants, giving both upper and lower bounds on query complexity. These problems include testing whether $\D$ is the uniform distribution $\calU$; testing whether $\D = \D^\ast$ for an explicitly provided $\D^\ast$; testing whether two unknown distributions $\D_1$ and $\D_2$ are equivalent; and estimating the variation distance between $\D$ and the uniform distribution. At a high level our main finding is that the new "conditional sampling" framework we consider is a powerful one: while all the problems mentioned above have $\Omega(\sqrt{N})$ sample complexity in the standard model (and in some cases the complexity must be almost linear in $N$), we give $\poly(\log N, 1/\eps)$-query algorithms (and in some cases $\poly(1/\eps)$-query algorithms independent of $N$) for all these problems in our conditional sampling setting. *Independently from our work, Chakraborty et al. also considered this framework. We discuss their work in Subsection [1.4].