# Distribution of inbag matrix when sampling with replacement

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

• Is this what you are looking for arxiv.org/pdf/1602.05822.pdf? Aug 13, 2019 at 10:00
• @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. Aug 13, 2019 at 13:37

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.