Testing Monotone Continuous Distributions on High-dimensional Real Cubes
Testing Monotone Continuous Distributions on High-dimensional Real Cubes
复制标题
测试高维实立方体上的单调连续分布
DOI：
10.1137/1.9781611973075.6
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Adamaszek M
中科院分区：
文献类型：
--
作者：
Adamaszek M
我们研究测试概率分布特性的任务。我们考虑这样一个场景：我们可以访问具有无限（甚至不可数）支持的未知分布的独立样本。我们的目标是测试是否具有给定的属性，或者是否与它相距 ε-远（在统计距离上，使用 L1-距离度量）。不难看出，对于无限或不可数域上的许多自然分布，不存在测试算法，我们研究的中心目标是了解是否存在可以有效测试的非平凡分布。例如，很容易看出，没有测试算法可以测试 [0, 1] 上给定的概率分布是否均匀。然而，我们表明，如果已知有关输入分布的一些附加信息，则可以测试均匀分布。我们将 Rubinfeld 和 Servedio (STOC'2005) 关于测试布尔维立方体上单调分布的均匀性的最新结果扩展到连续 [0, l]n 立方体的情况。我们证明，如果 [0, l] 上的分布是单调的，则可以测试是否与样本复杂度 (n/ε2) 一致。该结果在多对数因子下是最优的。
We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution with infinite (perhaps even uncountable) support. Our goal is to test whether has a given property or it is ε-far from it (in the statistical distance, with theL1-distance measure).It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0, 1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Booleann-dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case ofcontinuous[0, l]ncubes. We show that if a distribution on [0, l]nis monotone, then one can test if is uniform with the sample complexity (n/ε2). This result is optimal up to a polylogarithmic factor.