If a simple random sample (with replacement) of size $n$ is drawn from a population of size $N$, where $N \leq n$. Then what is the probability that all the population units (items) are present in the sample?

  • $\begingroup$ This is solved using inclusion-exclusion. Let $A_i$ be the event that the $i$-th number is not drawn. You seek $1-P(A_1 \cup \cdots \cup A_N)$. You can turn the grand union into a set of intersections using the rules for accounting for intersections. I solved a similar problem recently here at Cross Validated recently. stats.stackexchange.com/questions/389032/… If you follow the general form of the solution but use statistics appropriate for your specific problem, you will find the answer. $\endgroup$ – Peter Leopold Feb 3 at 4:21

This problem is a special case of the classical occupancy problem. If you conduct simple random sampling with replacement, choosing $n$ objects from a population of $N$, then the number $K$ of sampled items has a classical occupancy distribution with probability mass function:

$$\mathbb{P}(K=k|N,n) = \frac{(N)_k \cdot S(n,k)}{N^n} \quad \quad \quad \text{for all } 1 \leqslant k \leqslant \min(N,n),$$

where $(N)_k = N(N-1)(N-2) \cdots (N-k+1)$ are the falling factorials and $S(n,k)$ are the Stirling numbers of the second kind. The properties of this distribution are well-known (see e.g., Johnson and Kotz 1977). In your particular problem you are dealing with the case where $N \leqslant n$ seeking the probability that all population objects are sampled, which is:

$$\mathbb{P}(K=N|N,n) = \frac{N! \cdot S(n,N)}{N^n}.$$

These values can easily be calculated for values of $n$ and $N$ that are not too large. For large values the occupancy distribution can be approximated by the normal density.

Johnson, N.L. and Kotz, S. (1977) Urn Models and their Applications. John Wiley and Sons: New York.


Comment: You may want to check your analytic answer (approximately) against a simulation to make sure you have done the combinatorial analysis correctly.

Here is a simulation for $n = 12$ and $N = 25.$ You might think of it as a kind of 'reversal' of the famous birthday problem. Birth months equally likely. Room of 25 students. What is the probability all 12 months are represented? The answer is about $18\%.$

set.seed(2019);  pop = 1:12;  N = 25
x = replicate( 10^6, length(unique(sample(pop, N, repl=T))) )
mean(x);  mean(x == 12);  2*sd(x == 12)/1000
[1] 10.63755       # aprx E(X)
[1] 0.181771       # aprx P(X = 12)
[1] 0.0007713117   # 95% margin of sim error for P(X = 12)

       6        7        8        9       10       11       12 
0.000029 0.000944 0.014487 0.097603 0.301636 0.403530 0.181771 

With a million iterations, you can expect two, maybe three, place accuracy.

Also, if you consider the the number $N$ required on average to see all $n$ objects in the population, then you have the much studied 'coupon collecting' problem.


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