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 < α or > β on distributions over [n] requires n ~(α/β-o(1)) samples, and distinguishing whether a pair of distributions has statistical distance < α or > β 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 Ω(n ~(2/3)) samples.