Testing monotone high‐dimensional distributions

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 L 1 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