On the power of conditional samples in distribution testing
On the power of conditional samples in distribution testing
复制标题
论分布测试中条件样本的威力
DOI：
10.1145/2422436.2422497
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
A. Matsliah
中科院分区：
文献类型：
--
作者：
Sourav Chakraborty;E. Fischer;Yonatan Goldhirsh;A. Matsliah
在本文中，我们在分布特性测试的背景下定义并检验了条件采样预言的威力。离散分布 μ 的条件采样预言机将域的子集 S ⊂ [n] 作为输入，并输出根据 μ 绘制的随机样本 i ∈ S，以 S 为条件（并且独立于所有先前样本）。条件采样预言机是普通采样预言机的自然推广，其中 S 始终等于 [n]。我们表明，使用条件采样预言机，测试均匀性、测试与已知分布的同一性以及测试分布的任何标签不变属性比使用普通采样预言机更容易。另一方面，我们还表明，对于某些分布属性，即使使用条件采样，样本复杂性仍接近最大。
In this paper we define and examine the power of the conditional sampling oracle in the context of distribution-property testing. The conditional sampling oracle for a discrete distribution μ takes as input a subset S ⊂ [n] of the domain, and outputs a random sample i ∈ S drawn according to μ, conditioned on S (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which S always equals [n]. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample complexity remains near-maximal even with conditional sampling.