# understanding generalized coupon collector for distributions or learning mixture of distribution

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$$.

• 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. – D.W. May 18 at 23:40
• 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$... – Clement C. May 19 at 2:54
• Could you clarify your question? – Clement C. May 22 at 3:44