Testing probability distributions using conditional samples
Testing probability distributions using conditional samples
复制标题
使用条件样本测试概率分布
DOI：
10.1137/130945508
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
C. Canonne;D. Ron;R. Servedio
我们研究了一个新的框架，概率分布的属性测试，通过考虑分布测试算法，有条件的抽样预言。这是一个oracle，它将未知概率分布$D$的域$[N]$的子集$S \subseteq [N]$作为输入，并从限制为$S$的条件概率分布$D$返回一个平局。这种新的模型允许相当大的灵活性分布测试算法的设计，特别是，在这个模型中的测试算法可以是自适应的。
我们研究了广泛的自然分布测试问题，在这个新的框架和它的一些变种，查询复杂性的上限和下限。这些问题包括测试$D$是否是均匀分布$\mathcal{U}$;测试是否$D = D^\ast$对于显式提供的$D^\ast$;测试两个未知分布$D_1$和$D_2$是否等价;以及估计$D$和均匀分布之间的变化距离。在高层次上，我们的主要发现是，我们认为新的“条件抽样”框架是一个强大的框架：虽然上面提到的所有问题都有$\Omega（\sqrt{N}）标准模型中的$样本复杂度（在某些情况下，复杂度必须在$N$中几乎是线性的），我们给出$\mathrm{poly}（\log N，1/\vareps）$-查询算法（在某些情况下$\mathrm{poly}（1/\vareps）$-查询算法独立于$N$）在我们的条件采样设置的所有这些问题。
[2]独立于我们的工作，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 $\mathcal{U}$; 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 $\mathrm{poly}(\log N, 1/\varepsilon)$-query algorithms (and in some cases $\mathrm{poly}(1/\varepsilon)$-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].