Inclusion Probabilities In Bootstrap Samples

Why Inclusion Probabilities Matter

A bootstrap sample draws training observations with replacement. A case can therefore appear several times, or not appear at all. For tree ensembles, this distinction matters: the number of draws is not the number of distinct training cases represented. Inclusion probabilities quantify how likely each case is to appear at least once, while the complementary probability describes whether it is out-of-bag (OOB) for that resample.

The calculations depend on two sample sizes that should not be confused. Let $N$ be the number of distinct observations in the training data, and let $m$ be the number of independent draws made with replacement to form one bootstrap sample. In the conventional bootstrap, $m=N$, but the probability formulas also apply when the draw count differs from the training-set size.

Definition: For one bootstrap resample, a training observation is included if it appears at least once among the $m$ draws. It is out-of-bag (OOB) if it appears zero times. With uniform draws from the $N$ training observations, the inclusion and OOB probabilities for any specified observation are $$ P(\text{included})=1-\left(1-\frac{1}{N}\right)^m, \qquad P(\text{OOB})=\left(1-\frac{1}{N}\right)^m. $$

Deriving the Inclusion and OOB Probabilities

Assume each draw selects one of the $N$ training observations with probability $1/N$, and that the draws are independent. Fix one particular observation. On a single draw, the probability of not selecting it is $1-1/N$. To be OOB, it must be missed on every one of the $m$ draws. Independence means that the probabilities of these misses multiply.

P(\text{OOB}) = \underbrace{\left(1-\frac{1}{N}\right) \left(1-\frac{1}{N}\right)\cdots \left(1-\frac{1}{N}\right)}_{m\text{ independent draws}} = \left(1-\frac{1}{N}\right)^m.

Inclusion is the complementary event: the observation appears at least once, rather than zero times. Subtracting the OOB probability from one gives the inclusion probability. This derivation concerns one specified observation. It does not say that different observations’ inclusion events are independent; in fact, their indicators generally are not independent because the sample has a fixed number of draws.

Fix the observation.
For a specified training case, each draw misses it with probability $1-1/N$.

Find the OOB probability.
Multiply the miss probabilities across all $m$ independent draws: $P(\text{OOB})=(1-1/N)^m$.

Take the complement.
The probability of appearing at least once is $1-(1-1/N)^m$.

Expected Numbers of Unique and OOB Cases

A bootstrap sample has $N$ possible training cases, but the number actually represented varies from resample to resample. To find its expected number of unique cases, define an indicator for each case: it is 1 if that case is included and 0 otherwise. The total number of unique cases is the sum of those $N$ indicators. Each indicator has expectation equal to the common inclusion probability. By linearity of expectation, the expected total is the sum of the individual expectations. This argument does not require independence between the indicators.

E[\text{number of unique cases}] = N\left[1-\left(1-\frac{1}{N}\right)^m\right].

Likewise, the OOB count is the sum of indicators that equal 1 when a case is omitted. Its expectation is

E[\text{number of OOB cases}] = N\left(1-\frac{1}{N}\right)^m.

The two expected counts add to $N$, because every training case is either included at least once or OOB: $N[1-(1-1/N)^m]+N(1-1/N)^m=N$. These are expectations, not guarantees for any one resample; a realized sample can have more or fewer unique cases than its expected count.

Worked Example: A Conventional Bootstrap of Ten Cases

A hypothetical training set contains $N=10$ observations. One bootstrap sample is made using $m=10$ independent draws with replacement. Find the OOB and inclusion probabilities for a specified observation, then calculate the expected numbers of unique and OOB cases. Give probabilities and expected counts to four decimal places.

Method. Use the complement-of-no-selections calculation for a specified case, then multiply each probability by the ten cases to obtain the expected counts.

On one draw, the probability of missing the specified case is $1-1/10=9/10=0.9$. It must be missed on all ten draws to be OOB, so

P(\text{OOB})=0.9^{10}=0.3486784401.

Therefore its inclusion probability is

P(\text{included})=1-0.3486784401=0.6513215599.

There are ten cases, so the expected unique-case count is $10(0.6513215599)=6.513215599$, and the expected OOB count is $10(0.3486784401)=3.486784401$. Rounded to four decimal places, these are 6.5132 unique cases and 3.4868 OOB cases. As a check, $6.5132+3.4868=10.0000$.

Common mistake avoided: A sample of ten draws does not necessarily include all ten observations. Repeated selections use up draws without adding a new unique case.

The Familiar Large-Sample Proportions

For the conventional bootstrap, $m=N$. The OOB probability for a specified observation is then $(1-1/N)^N$, which approaches $e^{-1}$ as $N$ grows. Thus, for a sufficiently large conventional bootstrap, about $36.8\%$ of cases are OOB and about $63.2\%$ are included at least once. These are approximations to the finite-$N$ probabilities, not exact proportions for every training-set size.

The limiting result follows from the standard exponential limit $\lim_{N\to\infty}(1-1/N)^N=e^{-1}$. Taking the complement gives the limiting inclusion probability $1-e^{-1}$. The expected counts for a large conventional sample are correspondingly close to $0.368N$ OOB cases and $0.632N$ unique cases.

Worked Example: Large Conventional Bootstrap

A hypothetical data set has $N=1{,}000$ training observations, and a conventional bootstrap uses $m=1{,}000$ draws with replacement. Estimate the expected numbers of OOB and unique cases, using the exact finite-sample expression. Give the probabilities and counts to four decimal places.

Method. For one fixed observation, calculate the probability of being missed on all 1,000 draws. Its complement is the probability of appearing at least once.

P(\text{OOB})=\left(\frac{999}{1000}\right)^{1000} \approx 0.3676954, \qquad P(\text{included})=1-0.3676954\approx 0.6323046.

Multiplying by $N=1{,}000$, the expected OOB count is approximately $1{,}000(0.3676954)=367.6954$, and the expected unique-case count is approximately $1{,}000(0.6323046)=632.3046$. To four decimal places, the expected counts are 367.6954 OOB cases and 632.3046 unique cases. Their sum is 1,000.0000.

Common mistake avoided: Replacing the exact finite-sample probability by $e^{-1}$ is a useful approximation, but it is not the exact calculation for $N=1{,}000$. The approximation would give about 367.8794 OOB cases, rather than the exact-expression estimate of 367.6954.

Different Draw Counts and Repeated Resamples

The number $m$ of draws need not equal $N$. For example, if the resampling procedure specifies fewer draws than training cases, the same derivation applies with that smaller $m$. Increasing $m$ while holding $N$ fixed makes the OOB probability smaller, since $(1-1/N)^m$ decreases as $m$ increases. Consequently, the inclusion probability and expected number of unique cases increase.

A separate question concerns several independent bootstrap resamples. Let $q=(1-1/N)^m$ be the OOB probability in one resample for a fixed case. If $B$ resamples are independently generated, the probability the case is OOB in every one is $q^B$. The probability it is OOB at least once is the complement, $1-(1-q)^B$, because $1-q$ is its inclusion probability in one resample. Independence here is across the resamples, as stipulated; it is not an assumption that different cases behave independently within one resample.

Worked Example: A Small Sample With Several Resamples

A hypothetical training set has $N=4$ observations. Each bootstrap resample contains $m=2$ independent draws with replacement, and three such resamples are generated independently. Find (a) the probability that one specified case is OOB in a single resample, (b) the expected number of unique cases in one resample, and (c) the probability that the specified case is OOB at least once across the three resamples.

Method. First calculate the single-resample probabilities using $N=4,m=2$. Then use independence across the three resamples for part (c).

(a) A single draw misses the specified case with probability $1-1/4=3/4$. Therefore

P(\text{OOB in one resample})=\left(\frac{3}{4}\right)^2=\frac{9}{16}=0.5625.

(b) The inclusion probability in one resample is $1-9/16=7/16=0.4375$. The expected unique-case count is $4(7/16)=28/16=7/4=1.75$.

(c) The probability that the specified case is included in one resample is $7/16$. The probability it is included in all three independent resamples is $(7/16)^3=343/4096$. Thus the probability it is OOB at least once is

1-\left(\frac{7}{16}\right)^3 = 1-\frac{343}{4096} = \frac{3753}{4096} \approx 0.9163.

The result is plausible: being OOB at least once across three resamples is much more likely than being OOB in just one. Common mistake avoided: The event in part (c) is not “OOB in all three.” Its complement is “included in all three,” which is why the subtraction uses $(7/16)^3$.

Common Exam Traps

The most common error is treating a bootstrap sample as though it were drawn without replacement. With replacement, after one draw misses a case, the next draw still has probability $1-1/N$ of missing it. This repeated probability is why the miss probability is raised to the $m$th power.

For example, in a conventional sample with $N=m=10$, a tempting but incorrect calculation is to say that ten draws from ten cases must include every case, giving OOB probability zero. That would be true for a sample of ten distinct cases drawn without replacement. In a bootstrap sample, the correct calculation is $0.9^{10}=0.3486784401$, because a case can be selected more than once and another case consequently omitted.

Do not confuse $N$ and $m$. $N$ is the number of available training cases; $m$ is the number of draws. They coincide only in the conventional bootstrap.
Do not use $1-m/N$ as the exact OOB probability. It does not account for repeated draws. The exact OOB probability is $(1-1/N)^m$.
Do not interpret an expected count as a realized count. An expected 6.5 unique cases does not mean a particular resample contains a fractional case; it describes the average over repeated resampling.
Do not assume case indicators are independent. Linearity of expectation is enough to calculate expected counts; independence across cases is not needed.

Key takeaway: Under uniform, independent draws with replacement, a specified case is OOB with probability $(1-1/N)^m$ and included with probability $1-(1-1/N)^m$. Multiply these probabilities by $N$ to obtain the expected OOB and unique-case counts. For $m=N$ and large $N$, the proportions approach approximately 36.8% OOB and 63.2% included. These calculations are aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.

Check Your Understanding

For each problem, use independent draws with replacement and round probabilities or expected counts to four decimal places where appropriate.

A hypothetical training set has $N=8$ cases, and one conventional bootstrap sample uses $m=8$ draws. Find the OOB probability for a specified case and the expected number of unique cases. (Answer: OOB probability $=(7/8)^8\approx0.3436$; expected unique cases $=8[1-(7/8)^8]\approx5.2511$.)
A resample draws $m=6$ times from $N=12$ training cases. Find the inclusion probability for one specified case and the expected OOB count. (Answer: inclusion probability $=1-(11/12)^6\approx0.4067$; expected OOB count $=12(11/12)^6\approx7.1195$.)
A bootstrap sample draws $m=3$ times from $N=5$ cases. Find the expected number of unique cases. (Answer: $5[1-(4/5)^3]=2.4400$.)
A training set has $N=6$ cases, and each resample uses $m=6$ draws. Two independent resamples are generated. What is the probability that a specified case is OOB in at least one of them? (Answer: $1-[1-(5/6)^6]^2\approx0.5576$.)
A procedure draws $m=30$ times with replacement from $N=20$ training cases. Find the expected OOB count and expected unique-case count. (Answer: expected OOB count $=20(19/20)^{30}\approx4.2928$; expected unique-case count $=20[1-(19/20)^{30}]\approx15.7072$.)

What You'll Learn