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

CC BY-SA 4.0
2020-05-18T23:40:07.197Z
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.
CC BY-SA 4.0
2020-05-19T02:54:25.653Z
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.
CC BY-SA 4.0
2020-05-22T03:44:13.893Z
Could you clarify your question?
Clement C.
<ds.algorithms><pr.probability><lg.learning><randomized-algorithms><sample-complexity>
understanding generalized coupon collector for distributions or learning mixture of distribution
Annonymous
# understanding generalized coupon collector for distributions or learning mixture of distribution

(Asked by: username_0 on 2020-05-18)

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

**Tags:** ds.algorithms, pr.probability, lg.learning, randomized-algorithms, sample-complexity

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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$...  
> **username_2**: Could you clarify your question?  

---

## 0 answers

