# Why on average does each bootstrap sample contain roughly two thirds of observations?

I have run across the assertion that each bootstrap sample (or bagged tree) will contain on average approximately $2/3$ of the observations.

I understand that the chance of not being selected in any of $n$ draws from $n$ samples with replacement is $(1- 1/n)^n$, which works out to approximately $1/3$ chance of not being selected.

What is a mathematical explanation for why this formula always gives $\approx 1/3$ ?

-
I believe this is the origin of the $.632$ in the bootstrap 632+ rule. – gung Mar 6 '14 at 2:46

Essentially, the issue is to show that $\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$
(and of course, $e^{-1} =1/e \approx 1/3$, at least very roughly).

It doesn't work at very small $n$ -- e.g. at $n=2$, $(1- 1/n)^n=\frac{1}{4}$. It passes $\frac{1}{3}$ at $n=6$, passes $0.35$ at $n=11$, and $0.366$ by $n=99$. Once you go beyond $n=11$, $\frac{1}{e}$ is a better approximation than $\frac{1}{3}$.

The grey dashed line is at $\frac{1}{3}$; the red and grey line is at $\frac{1}{e}$.

Rather than show a formal derivation (which can easily be found), I'm going to give an outline (that is an intuitive, handwavy argument) of why a (slightly) more general result holds:

$$e^x = \lim_{n\to \infty} \left(1 + x/n \right)^n$$

(Many people take this to be the definition of $\exp(x)$, but you can prove it from simpler results such as defining $e$ as $\lim_{n\to \infty} \left(1 + 1/n \right)^n$.)

Fact 1: $\exp(x/n)^n=\exp(x)\quad$ This follows from basic results about powers and exponentiation

Fact 2: When $n$ is large, $\exp(x/n) \approx 1+x/n\quad$ This follows from the series expansion for $e^x$.

(I can give fuller arguments for each of these but I assume you already know them)

Substitute (2) in (1). Done. (For this to work as a more formal argument would take some work, because you'd have to show that the remaining terms in Fact 2 don't become large enough to cause a problem when taken to the power $n$. But this is intuition rather than formal proof.)

[Alternatively, just take the Taylor series for $\exp(x/n)$ to first order. A second easy approach is to take the binomial expansion of $\left(1 + x/n \right) ^n$ and take the limit term-by-term, showing it gives the terms in the series for $\exp(x/n)$.]

So if $e^x = \lim_{n\to \infty} \left(1 + x/n \right) ^n$, just substitute $x=-1$.

Immediately, we have the result at the top of this answer, $\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$

As gung points out in comments, the result in your question is the origin of the 632 bootstrap rule

e.g. see

Efron, B. and R. Tibshirani (1997),
"Improvements on Cross-Validation: The .632+ Bootstrap Method,"
Journal of the American Statistical Association Vol. 92, No. 438. (Jun), pp. 548-560

-

More precisely, each bootstrap sample (or bagged tree) will contain $1-\frac{1}{e} \approx 0.632$ of the sample.

Let's go over how the bootstrap works. We have an original sample $x_1, x_2, \ldots x_n$ with $n$ items in it. We draw items with replacement from this original set until we have another set of size $n$.

From that, it follows that the probability of choosing any one item (say, $x_1$) on the first draw is $\frac{1}{n}$. Therefore, the probability of not choosing that item is $1 - \frac{1}{n}$. That's just for the first draw; there are a total of $n$ draws, all of which are independent, so the probability of never choosing this item on any of the draws is $(1-\frac{1}{n})^n$.

Now, let's think about what happens when $n$ gets larger and larger. We can take the limit as $n$ goes towards infinity, using the usual calculus tricks (or Wolfram Alpha): $$\lim_{n \rightarrow \infty} \big(1-\frac{1}{n}\big)^n = \frac{1}{e} \approx 0.368$$

That's the probability of an item not being chosen. Subtract it from one to find the probability of the item being chosen, which gives you 0.632.

-

Sampling with replacement can be modeled as a sequence of binomial trials where "success" is an instance being selected. For an original dataset of $n$ instances, the probability of "success" is $1/n$, and the probability of "failure" is $(n-1)/n$. For a sample size of $b$, the odds of selecting an instance exactly $x$ times is given by the binomial distribution:

$$P(x,b,n) = \bigl(\frac{1}{n}\bigr)^{x} \bigl(\frac{n-1}{n}\bigr)^{b-x} {b \choose x}$$

In the specific case of a bootstrap sample, the sample size $b$ equals the number of instances $n$. Letting $n$ approach infinity, we get:

$$\lim_{n \rightarrow \infty} \bigl(\frac{1}{n}\bigr)^{x} \bigl(\frac{n-1}{n}\bigr)^{n-x} {n \choose x} = \frac{1}{ex!}$$

If our original dataset is big, we can use this formula to compute the probability that an instance is selected exactly $x$ times in a bootstrap sample. For $x = 0$, the probability is $1/e$, or roughly $0.368$. The probability of an instance being sampled at least once is thus $1 - 0.368 = 0.632$.

Needless to say, I painstakingly derived this using pen and paper, and did not even consider using Wolfram Alpha.

-

Just adding to @retsreg's answer this can also be demonstrated quite easily via numerical simulation in R:

N <- 1e7 # number of instances and sample size
bootstrap <- sample(c(1:N), N, replace = TRUE)
round((length(unique(bootstrap))) / N, 3)
## [1] 0.632

-

This can be easily seen by counting. How many total possible samples? n^n. How many NOT containing a specific value? (n-1)^n. Probability of a sample not having a specific value - (1-1/n)^n, which is about 1/3 in the limit.

-