Expected proportion of the sample when bootstrapping

suppose you have a sample of size $N$ that for some reason you want to bootstrap to produce a sample of size $M$. I am trying to produce a closed form solution for the expected proportion of the sample that will be present when I bootstrap a sample. I have not been able to produce it, however, I have used Matlab to come up with a numerical approximation.

I took a sample of size 100 and produced bootstrap 300 samples of sizes varying from 1 to 500. For a fixed bootstrap sample size, I later estimated the mean proportion of the original sample that got into the bootstrapped sample by averaging over the number of unique values. This is what I got: Any ideas on how to produced the closed form for this number?

This is related to collision-counting in the birthday problem.

Imagine you walk into a room of $k$ people. The probability at least one shares a birthday with you is $q(k;n) = 1 - \left( \frac{n-1}{n} \right)^k$, where $n$ is the number of different birthday slots (days in the year).

The expected number you add to the total number of different birthdays in the room when you walk in is therefore $1-q(k;n)=\left( \frac{n-1}{n} \right)^k$

So by the law of iterated expectations, the expected number of different birthdays after $m$ people have entered is

$\sum_{i=1}^m \left( \frac{n-1}{n} \right)^{i-1} = \sum_{i=0}^{m-1} \left( \frac{n-1}{n} \right)^i$

This is sum to $m$ terms of a geometric series, which is straightforward:

$\hspace{2.3cm} = \frac{1- \left( \frac{n-1}{n} \right)^m}{1-\frac{n-1}{n}}=n\left[1- \left( \frac{n-1}{n} \right)^m\right]$

Check: at n=100, m=50 this gives $\approx$ 39.4994, while simulation gives:

> mean(replicate(10000,length(unique(sample(1:100,50,replace=TRUE)))))
 39.4938

so that looks okay.

The expected fraction is then $\frac{1}{n}$th of that, $1- \left( \frac{n-1}{n} \right)^m$.

Note that if $n$ is large, $(1-\frac{1}{n})^n\approx e^{-1}$, so if $m$ is some value that's at least a large fraction of $n$, $(1-\frac{1}{n})^m\approx e^{-\frac{m}{n}}$, so we get that the expected number is approximately $n (1- e^{-\frac{m}{n}})$.

Let's try that approximation on the above example where $m=50$ and $n=100$: $100 (1-e^{-\frac{50}{100}})=100(1-e^{-\frac{1}{2}})\approx 39.347$, which is fairly close to the exact answer - for a given $m/n$ it improves with larger $n$.

So a quick and reasonably accurate approximation to the fraction is $(1- e^{-\frac{m}{n}})$.

Note that when $m=n$ this gives the usual "0.632" rule.

• Everything is clear for me except where you take the law of iterated expectations (not your fault, I am a little bit rusty). I will carefully revise that part to add it to the argument. – MathUser Dec 1 '14 at 9:25
• The point there is basically just "you get an expectation by taking the expectation of conditional expectations". There's nothing fancy going on; it's just justifying that the average proportion is the sum of all the individual conditional expectations divided by $n$ at the end. There are other ways to justify that calculation, though. – Glen_b Dec 1 '14 at 10:14
• So I get that the $\mathbb{E}(X) = \sum_i\mathbb{E}(X\vert A_i) \mathbb{P}(A_i)$ but I don't see how are you using that to convert it to $\sum_{i=1}^m \left( \frac{n-1}{n} \right)^{i-1}$. – MathUser Dec 2 '14 at 19:23
• By the way, I just plotted your answer against my simulation and they are basically the same line. – MathUser Dec 2 '14 at 19:46
• It's always important to check such answers in exactly that way. I'll try to clarify the reasoning better as soon as I can. – Glen_b Dec 2 '14 at 22:05

I would like to corroborate again the answer from @glen-b with some experimental results.

I wrote a function $p(n,m,k)$ that tells the exact probability (is not based on simulations) of getting exactly $k$ unique elements after choosing $m$ samples with replacement from a set of $n$ elements. Notice $p$ is a pdf on $k$.

For example, if choosing 600 from 600, the expected value of $k$ is close to $600*(1-e^{-1}) \approx = 379$. It's pdf is shown in blue. Then, I used the function $p$ to compute the expected value of $k$ and plotted my results (orange) against the formula @glen-b provided (green). As expected, the outputs were exactly the same. And here's the code. The simulation function is added as a reference. It is never used to compute $p$ or the expected $k$. The computation of $p$ is done in python 3 and is based on Dynamic Programming DP:

import numpy as np
from functools import lru_cache
import sys; sys.setrecursionlimit(5000000)

def simulation(n, m):
''' From n, choose m and count unique values'''
x = np.arange(n)
s = np.random.choice(x, n, replace=True)
k = len(np.unique(s))
return k

@lru_cache(None)
def p(n,m,k):
'''Prob. of simulation(n,m) = k. Requires 1<=n and 0<=k<=m'''
if k==0 or n==1 or k>m:
ans = int(m==k)
else:
ans = p(n,m-1,k) * k/n + p(n,m-1,k-1) * (n-k+1)/n
return ans

def expected_k(n):
'''Expected output of simulation(n,n) / n. DP version'''
K = np.arange(n+1)
P = np.array([p(n,n,k) for k in K])
return np.multiply(K,P).sum()/n