TESTING SYMMETRIC PROPERTIES OF DISTRIBUTIONS

We introduce the notion of a canonical tester for a class of properties on distributions, that is, a tester strong and general enough that a distribution property in the class is testable if and only if the canonical tester tests it. We construct a canonical tester for the class of properties of one or two distributions that are symmetric and satisfy a certain weak continuity condition. Analyzing the performance of the canonical tester on specific properties resolves two open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy < alpha or > beta on distributions over [n] requires n(alpha/beta-o(1)) samples, and distinguishing whether a pair of distributions has statistical distance < alpha or > beta requires n(1-o(1)) samples. Our techniques also resolve a conjecture about a property that our canonical tester does not apply to: distinguishing identical distributions from those with statistical distance > 1/2 requires Omega(n(2/3)) samples.