Testing Properties of Collections of Distributions
Testing Properties of Collections of Distributions
复制标题
测试分布集合的属性
作者：
Reut Levi;D. Ron;R. Rubinfeld
我们提出了一个研究分布集合的性质测试的框架，其中集合中分布的个数是问题的一个参数。以前关于分布的属性测试的工作被认为是单一分布或成对分布。我们建议两个模型，在给予算法访问分布样本的方式上有所不同。在一个模型中，算法可以从其选择的任何分布中要求样本，而在另一个模型中，分布的选择是随机的。我们的主要焦点是区分集合中所有分布相同(或非常相似)的情况和必须以不可忽略的方式修改集合中的分布以获得这一性质的情况的基本问题。我们给出了这个测试问题的几乎严格的上界和下界，并研究了一个可聚类性的扩展。我们的一个下限直接意味着测试联合分布的独立性的下限，这一结果在以前的工作中是开放的。
We propose a framework for studying property testing of collections of distributions, where the number of distributions in the collection is a parameter of the problem. Previous work on property testing of distributions considered single distributions or pairs of distributions. We suggest two models that differ in the way the algorithm is given access to samples from the distributions. In one model the algorithm may ask for a sample from any distribution of its choice, and in the other the choice of the distribution is random. Our main focus is on the basic problem of distinguishing between the case that all the distributions in the collection are the same (or very similar), and the case that it is necessary to modify the distributions in the collection in a non-negligible manner so as to obtain this property. We give almost tight upper and lower bounds for this testing problem, as well as study an extension to a clusterability property. One of our lower bounds directly implies a lower bound on testing independence of a joint distribution, a result which was left open by previous work.