Testing monotone high‐dimensional distributions
Testing monotone high‐dimensional distributions
复制标题
测试单调高维分布
DOI：
10.1145/1060590.1060613
复制
发表时间：
2005
影响因子：
1
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
R. Rubinfeld;R. Servedio
如果订单中的y≥x，则在A（部分）有序域上的单调分布P具有p（y）≥p（x）。从测试的分布中随机绘制。 Boolean Cube的已知等速度不平等的概括。我们的统一性测试算法是最佳的，这是多数因素（n）因素，并且在其他几个问题的复杂性上给出了指数下限（测试单调分布是否为与固定的单调产物分布相同，并近似于单调分布的熵）
A monotone distribution P over a (partially) ordered domain has P(y) ≥ P(x) if y ≥ x in the order. We study several natural problems of testing properties of monotone distributions over the n‐dimensional Boolean cube, given access to random draws from the distribution being tested. We give a poly(n)‐time algorithm for testing whether a monotone distribution is equivalent to or ϵ‐far (in the L1 norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on testing monotone distributions over the n‐dimensional Boolean cube, based on a new decomposition technique for monotone distributions. We use this method to show that our uniformity testing algorithm is optimal up to polylog(n) factors, and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or ϵ‐far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009