Say I take a random sample of size $M$ from a sample of size $N$, like, for example you'd do when bootstrapping in random forest.

As you increase $M$, you're more likely to sample any particular observation an increasing number of times.

When $M = N$, it's been shown that you get zero instances of any given element about .38 percent of the time.

I want to know what this distribution of the inbag matrix is -- the distribution of counts over elements -- as $M$ is varied.

To see random draws of this distribution for $N = 26$ and $M = 10$, you can run this a bunch of times:

data.frame(table(table(sample(letters[1:26], 10, replace = T))))

I'm looking for an analytical function to give me the expectation of how many times ecah inbag count will show up as a function of $M$ and $N$.

  • $\begingroup$ Is this what you are looking for arxiv.org/pdf/1602.05822.pdf? $\endgroup$ Aug 13, 2019 at 10:00
  • $\begingroup$ @user2974951 sort of. I could probably use the results in that paper to get what I want, which is the distribution over the number of times each element is sampled given N and M. But reading that paper is edifying at minimum because it confirms that the problem is hard. $\endgroup$ Aug 13, 2019 at 13:37

1 Answer 1


This is an example of the classical occupancy problem which leads to the classical occupancy distribution. Let $1 \leqslant K \leqslant \min(M,N)$ denote the number of different values that are resampled. Then the probability mass function for this random variable is the classical occupancy distribution:

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

where $(N)_k = N(N-1)(N-2) \cdots (N-k+1)$ are the falling factorials and $S(M,k)$ are the Stirling numbers of the second kind. Letting $E_r \equiv (1-r/N)^M$, 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 properties of this distribution and methods for its computation are well-known (for details on the properties and computation of this distribution, see e.g. O'Neill 2020). For large values of $M$ and $N$ you can approximate it well by a normal distribution with identical mean and variance.


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.