How many neglected samples when drawn with replacement? (bagging)

Question

I learned a while ago about an interesting place that $e$ shows up in probability: if there are $n$ items and you sample $n$ times with replacement, you would expect that the fraction of samples that is drawn is $1 - e^{-1} ≈ 0.63$, and the fraction of samples that never gets drawn is $e^{-1} ≈ 0.37$ (assuming sufficiently large $n$).

This comes up in the context of "bagging" in machine learning. A "bagged" model does not train on all $n$ data points, but trains on $n$ samples drawn randomly with replacement. If there are 100 samples, about 63 will be drawn on average (i.e. many of them will be drawn more than once while 37 are neglected).

I wanted to derive this using a random variable. I started with a random variable $X$ which represents the number of samples that are drawn at least once. The goal is to compute $E[X]$.

$$E[X]$$ $$\sum_{x=1}^{n}x * p_{X}(x)$$ $$\sum_{x=1}^{n}x * \frac{{n \choose x} {n - x + x - 1 \choose x - 1}}{{n + n - 1 \choose n}}$$

The term $n \choose x$ is from choosing the precise samples that will be drawn from.

The term $n - x + x - 1 \choose x - 1$ is from the following: We have exactly $x$ samples that we are considering drawing from. We allot the minimum number of draws so that we can guarantee each sample has 1 draw. This means there are $(n - x)$ remaining samples to allot into the $x$ buckets. We use the stars and bars technique to take $n-x$ indistinct draws with replacement from $x$ samples to obtain the binomial coefficient expression.

The term $n + n - 1 \choose n$ counts all the ways you can take $n$ indistinct draws with replacement from $n$ samples.

When I compute this for reasonably sized $n$, I do not get $63\%$ of samples that have been drawn, but instead I get closer to $50\%$. Here is some Python:

>>> from math import comb
>>> n = 100
>>> sum(x * comb(n, x) * comb(n - 1, x - 1) for x in range(1, n + 1)) / comb(n + n - 1, n)
50.25125628140704

I know I am using a valid distribution because I can sum just the probabilities: $\sum_{x=1}^{n}\frac{{n \choose x} {n - x + x - 1 \choose x - 1}}{{n + n - 1 \choose n}} = 1.0$

>>> sum(comb(n, x) * comb(n - 1, x - 1) for x in range(1, n + 1)) / comb(n + n - 1, n)
1.0

I have two questions:

• My expression must be wrong to model this problem. How would I have to change my expression to make $E[X] / n = 1 - e^{-1} ≈ 0.63$? I know there are alternative proofs for this fact, but I want to know why my proof is failing.
• Even if my random variable $X$ is not the correct one to model this problem, I am curious if there is some standard distribution it corresponds to? $X \sim Mystery(n); p_{X}(x) = \frac{{n \choose x} {n - x + x - 1 \choose x - 1}}{{n + n - 1 \choose n}}$

Answer 1

Your probabilities are wrong. Take $x=1$ for example. Choosing only one of the samples $n$ times has the probability $$P(x=1)={n\choose 1}\frac{1}{n^n}=\frac{1}{n^{n-1}}$$

However, in your formula, it is $\frac{n}{2n-1\choose n}$.

In probability calculations, counting approaches sometimes can mislead because some objectives care for (in)distinguishability. However, distinct or not, every granular outcome has unit probability mass and when grouped together, they'll add up to the mass of the grouped object.

Edit: (Answering for your comment below, since it'd be quite long there)

If we have two elements ($n=2$) in our set, i.e. $\mathcal S=\{s_1,s_2\}$, and we draw two samples with replacement, we'll have four possible outcomes: $\{(s_1,s_1),(s_1,s_2),(s_2,s_1),(s_2,s_2)\}$, where the binary tuples refer to $(\text{draw 1 outcome},\text{draw 2 outcome})$.

$x=1$ case is interested only in the outcomes $(s_1,s_1)$ and $(s_2,s_2)$, where both outcomes are the same. So, the probability of having one distinct sample out of two draws is $1/2$.

The reason for your formula being wrong is that $(s_1,s_2)$ and $(s_2,s_1)$ are actually different outcomes, and their probabilities add up for $x=2$. Consider a simpler case where you have a fair coin and you want to know the probability of obtaining either all Heads or all Tails in your draws. There are four possible outcomes of your draws: $(H,H),(H,T),(T,H),(T,T)$, and the event you're interested in is the subset $(H,H),(T,T)$. The probability of this event is $1/2$. This setup is exactly the same as above.

In a nutshell, you can't always group cases where objects are indistinguishable like you do in counting problems.

Answer 2

The correct derivation is:

$$E[X]$$ $$\sum_{x=1}^{n} x * p_{X}(x)$$ $$\sum_{x=1}^{n} x * \frac{{n \choose x} \left(\sum_{i=0}^{x} (-1)^{i} {x \choose i} (x - i)^{n} \right)}{n^{n}}$$

• The term ${n \choose x}$ is from choosing the precise samples that will be drawn from (as noted above).
• The term $\sum_{i=0}^{x} (-1)^{i} {x \choose i} (x - i)^{n}$ is a Stirling number of second kind (technically it is a Stirling number of second kind multiplied by $x!$). It is necessary here because it allows us to count all the ways to make $n$ distinct draws from $x$ samples with the constraint that each sample must be drawn at least once.
• The term $n^{n}$ counts all the ways you can take $n$ distinct draws with replacement from $n$ samples.

As @gunes noted, we should be thinking in terms of distinct draws rather than indistinct. This is confusing because the "draws" themselves don't seem distinguishable, so why consider them distinct? I think it is because we want each selection (that is, a particular assignment of the draws to the samples) to be "weighted" as if the draws were distinct.

To take the example from my comment on @gunes answer, "Assume n=2. There are three possible outcomes: both draws for sample1, both draws for sample 2, and one draw on each." It remains true that there are three possible outcomes, but I think the caveat is that we want the selection "one draw on each" to be "weighted" twice as much (i.e. count as if we were making distinct draws, and then merging the selections that looked alike under an indistinct interpretation).

The expected value computes as originally desired: $\lim_{n \to \infty} \frac{1}{n} E[X] = \lim_{n \to \infty} \frac{1}{n} \sum_{x=1}^{n} x * \frac{{n \choose x} \left(\sum_{i=0}^{x} (-1)^{i} {x \choose i} (x - i)^{n} \right)}{n^{n}} = 0.63... = 1 - e^{-1}$

>>> from math import comb
>>> n = 100
>>> 1/n * sum(x * comb(n, x) * sum((-1) ** i * comb(x, i) * (x - i) ** n for i in range(x + 1)) for x in range(1, n + 1)) / n ** n
0.6339676587267705

The probabilities sum to one: $\sum_{x=1}^{n} \frac{{n \choose x} \left(\sum_{i=0}^{x} (-1)^{i} {x \choose i} (x - i)^{n} \right)}{n^{n}} = 1$

>>> sum(comb(n, x) * sum((-1) ** i * comb(x, i) * (x - i) ** n for i in range(x + 1)) for x in range(1, n + 1)) / n ** n
1.0