# Sample all elements from a set at least once, with replacement

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?

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

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