Testing equivalence between distributions using conditional samples

We study a recently introduced framework [7, 8] for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. This is an oracle that takes as input a subset S ⊆ [ N ] of the domain [ N ] of the unknown probability distribution D and returns a draw from the conditional probability distribution D restricted to S. This model allows considerable flexibility in the design of distribution testing algorithms; in particular, testing algorithms in this model can be adaptive. In this paper we focus on algorithms for two fundamental distribution testing problems: testing whether D = D * for an explicitly provided D and testing whether two unknown distributions D 1 and D are equivalent. For both problems, the sample complexity of testing in the standard model is at least. For the first problem we give an algorithm in the conditional sampling model that performs only poly(1/∊)-queries (for the given distance parameter ∊) and has no dependence on N. This improves over the poly(log N, 1/∊)-query algorithm of [8]. For the second, more difficult problem, we given an algorithm whose complexity is poly(log N, 1/∊). For both problems we also give efficient algorithms that work under the restriction that the algorithm perform queries only on pairs of points and provide a lower bound that is polynomial in the upper bounds.

Authors

• Clément L. Canonne
• Dana Ron
• Rocco A. Servedio

Keywords

No keywords are indexed for this paper.