C. Canonne and D. Ron and R. Servedio.

In

We study a recently introduced framework
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 \subseteq [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^\ast$ for an explicitly provided $\D^\ast$, and testing whether two unknown distributions $\D_1$ and $\D_2$ are equivalent. We give two efficient algorithms for each of these two problems. At a high level our main finding is that the new ``conditional sampling'' framework we consider is a powerful one: while both these problems above have $\Omega(\sqrt{N})$ sample complexity in the standard model we give $\poly(\log N, 1/\eps)$-query algorithms (and in some cases $\poly(1/\eps)$-query algorithms independent of $N$) for both of them in our conditional sampling setting.

pdf of conference version

Link to arxiv version of full paper