2
$\begingroup$

I've seen the Coupon collector's problem and I believe this is a variant of it but I can't quite wrap my head around it. This is not a homework assignment.

I have a set of k elements. I randomly sample s elements from the set and then replace them. If I do this n times, what is the probability that I will have sampled every single element at least once?

$\endgroup$
  • 1
    $\begingroup$ Consider using inclusion-exclusion on the events "I did not find the $i$'th element in any of the attempts." $\endgroup$ – JMoravitz Oct 16 '19 at 20:16
  • $\begingroup$ Is your sample of $s$ elements without replacement? I.e. are they guaranteed to be distinct? $\endgroup$ – Henry Oct 16 '19 at 23:35
  • $\begingroup$ Good question. Yes, the sample is without replacement. $\endgroup$ – willow1986 Oct 17 '19 at 13:41
2
$\begingroup$

I don't yet have the solution in closed form, but I'll leave this here as it gives a computable expression for this probability, and perhaps can be used to find a more ideal solution.

Let $A_i$ be the event that the $i$th element of the $k$ is never sampled in the course of this process. We wish to compute $P((\bigcup A_i)^c) = 1 - P(\bigcup A_i)$. This quantity can be written, by the principle of inclusion exclusion, as $$ \sum_{i=0}^k (-1)^{i} \sum_{J\subset [1,\ldots,k], \lvert J\rvert = i} P(A_J), $$ where $A_J = \bigcap_{j\in J} A_j$. First we need to compute the $P(A_J)$. This is the probability that a fixed set $J$ of the elements is never sampled throughout the process. This happens in one trial with probability $\frac{\binom{ k-\lvert J\rvert}{s}}{\binom{k}{s} }$. The trials are independent, so the probability that it happens in all trials is the $n$th power of this. Substituting into the above expression, the result is given by $$ \frac{1}{\binom{k}{s}^n } \sum_{i=0}^k (-1)^{i} \sum_{J\subset [1,\ldots,k], \lvert J\rvert = i} \binom{ k-\lvert J\rvert}{s}^n $$ $$ = \frac{1}{\binom{k}{s}^n } \sum_{i=0}^k (-1)^{i} \binom{k}{i} \binom{ k-i}{s}^n $$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.