Suppose we sample (uniformly, with replacement) $t$ times a set of $N$ items. What is the probability $x$ that the sample contains $y$ different items?

This is representative of a real-life scenario I am facing, trying to determine if a certain issue impacts the whole population, or is specific to a certain subset. For example, I have a population of 73 specimens ($N$). One issue has manifested 250 times ($t_1$) on 47 different specimens ($y_1$), while another has manifested 64 times ($t_2$) on 17 different specimens ($y_2$). Intuitively, issue 2 is much more likely to be specific to a subset of the specimens, but I would like to quantify this before trying to analyse further.

One way forward I struggled with for a while was to use the inclusion probability. There are formulas for including one item $x_k$ or two items $x_{kl}$ (below), but I couldn't generalize for $y$ items.

$$x_k = (1-\frac{1}{N})^t $$ $$x_{kl} = 2(1-\frac{1}{N})^t - (1-\frac{2}{N})^t $$

I also have a little simulation to get some taste of what the distribution would look like.

Any help or direction would be appreciated!


1 Answer 1


This is an example of the classical occupancy problem. Let $1 \leqslant K \leqslant \min(t,N)$ denote the number of different items sampled. Then the probability mass function for this random variable is the classical occupancy distribution:

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

where $(N)_k = N(N-1)(N-2) \cdots (N-k+1)$ are the falling factorials and $S(t,k)$ are the Stirling numbers of the second kind. Letting $E_r \equiv (1-r/N)^t$, the mean and variance of the distribution are:

$$\mathbb{E}(K) = N (1-E_1) \quad \quad \quad \quad \quad \mathbb{V}(K) = N [(N-1) E_2 + E_1 - N \cdot E_1^2].$$

The higher-order moments and other broader properties of this distribution are well-known (see e.g., O'Neill 2019). For large values of $t$ and $N$ you can approximate it well by a normal distribution with identical mean and variance, with approximation accuracy shown in the cited paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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