Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from the distribution $P$, can we learn $T_1$ and $T_2$? Clearly, using a coupon collector argument, we can learn $T_1\cup T_2$ using $O(n \log n)$ samples from $P$ and suppose $T_2$ was empty, we can learn $T_1$ completely. But is there a way where we can learn both $T_1$ and $T_2$ individually? I don't mind even allowing $poly(n)$ many samples from the distribution $P$.

  • 1
    $\begingroup$ What does it mean to say that $P$ is the uniform distribution over $T_1,T_2$? Do you mean that $P$ is the uniform distribution over $T_1 \cup T_2$? I find the problem statement unclear. Please edit the question to define the distribution $P$ more clearly. $\endgroup$ – D.W. May 18 '20 at 23:40
  • $\begingroup$ As stated, I don't think the question is well-posed. Are $T_1,T_2$ disjoint? If $P$ is uniform over $T_1\cup T_2$ where $T_1,T_2$ are disjoint, there is no identifiability of the sets. Even knowing perfectly the pmf of $P$ (equivalently, the $2m$ points of the support), there are $\binom{2m}{m}$ equally valid choices for $T_1$... $\endgroup$ – Clement C. May 19 '20 at 2:54
  • $\begingroup$ Could you clarify your question? $\endgroup$ – Clement C. May 22 '20 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.