Bootstrap Sampling And Out-Of-Bag Observations

Why Bootstrap Samples Contain Repeats

A random forest is built from many trees, each fitted to a sample of the training data. In the standard bootstrap scheme, a tree receives $n$ draws with replacement from the $n$ training observations. Because sampling is with replacement, a row can be selected more than once, while another row may not be selected at all. The number of rows drawn is therefore $n$, but the number of distinct training observations in the sample is usually smaller than $n$.

This distinction matters in two ways. First, it describes how much of the original data typically appears in any one tree's training sample. Second, a training observation omitted from a particular tree's sample can be set aside when assessing that tree's prediction for that observation. Such a prediction is called an out-of-bag prediction for that case and tree.

Definition: A bootstrap sample of size $m$ from $n$ observations consists of $m$ independent draws, each made with replacement. In the ordinary, equally weighted bootstrap, each draw selects each observation with probability $1/n$. An observation is in bag for a tree if it is selected one or more times, and out of bag if it is selected zero times.

Inclusion and Omission Probabilities

Consider one particular observation. On a single uniform draw, its probability of not being selected is $1-1/n$. The draws are independent, so the probability it is not selected on any of the $m$ draws is the product of the $m$ single-draw probabilities.

P(\text{observation is OOB})=\left(1-\frac{1}{n}\right)^m

The event that the observation is selected at least once is the complement of being omitted throughout the sample. Thus:

P(\text{observation is in bag})=1-\left(1-\frac{1}{n}\right)^m

For the standard random forest bootstrap, $m=n$. As $n$ becomes large, the OOB probability approaches $e^{-1}$, about $0.3679$, and the in-bag probability approaches $1-e^{-1}$, about $0.6321$. These are large-sample approximations, not exact probabilities for a finite $n$.

Expected distinct observations: Let $I_i=1$ if observation $i$ appears at least once in the sample, and let $I_i=0$ otherwise. The number of distinct observations is $D=\sum_{i=1}^{n} I_i$. For a uniform bootstrap sample of size $m$, $$ E[D]=n\left[1-\left(1-\frac{1}{n}\right)^m\right]. $$ The expected number omitted is $n(1-1/n)^m$.

Why the Expected-Coverage Formula Holds

The indicator-variable argument gives the expected number of distinct observations without requiring the indicators to be independent. Each $I_i$ has expected value equal to the probability that observation $i$ appears at least once:

E[I_i]=P(I_i=1)=1-\left(1-\frac{1}{n}\right)^m

Since $D$ is the sum of these indicators, linearity of expectation gives $E[D]=\sum_{i=1}^{n}E[I_i]$. All $n$ observations have the same inclusion probability under uniform sampling, so:

E[D] =\sum_{i=1}^{n}\left[1-\left(1-\frac{1}{n}\right)^m\right] =n\left[1-\left(1-\frac{1}{n}\right)^m\right].

This derivation does not say that every bootstrap sample contains exactly $E[D]$ distinct observations. It gives the average number over repeated samples. Individual samples can contain more or fewer distinct rows.

Worked Example: Coverage in an Eight-Observation Bootstrap

A hypothetical training set contains $n=8$ claim records. One tree is fitted using $m=8$ uniform draws with replacement. Calculate the probability that a specified record is OOB, the expected number of distinct records in the sample, and the expected number of OOB records.

Method. Use the complement rule for one record, then multiply its inclusion or omission probability by the number of records to obtain the corresponding expected count.

Step 1: Probability the specified record is omitted. Its probability of being missed on one draw is $7/8$. It must be missed on all eight independent draws:

P(\text{OOB})=\left(\frac{7}{8}\right)^8 =\frac{5{,}764{,}801}{16{,}777{,}216} \approx 0.3436089.

Step 2: Probability it is included. Take the complement:

P(\text{in bag})=1-0.3436089\ldots =0.6563911\ldots

Step 3: Expected number of distinct records. There are eight records, each with the same inclusion probability:

E[D]=8(0.6563911\ldots)=5.2511287\ldots

To three decimal places, the expected number of distinct records is 5.251.

Step 4: Expected number of OOB records.

E[\text{OOB count}] =8(0.3436089\ldots)=2.7488713\ldots

To three decimal places, this is 2.749. The two expectations check: $5.2511287\ldots+2.7488713\ldots=8$. The method avoids confusing the omission probability with the inclusion probability.

When Draws Have Unequal Probabilities

The ordinary random forest bootstrap uses equal selection probabilities, but the same reasoning can be extended to draws with unequal probabilities. Suppose observation $i$ is selected on each draw with probability $p_i$, and the $m$ draws are independent. Its probability of being omitted on one draw is $1-p_i$, so its probability of being omitted on all draws is $(1-p_i)^m$. The expected number of distinct observations is then the sum of the individual inclusion probabilities.

P(i\text{ is included})=1-(1-p_i)^m, \qquad E[D]=\sum_{i=1}^{n}\left[1-(1-p_i)^m\right].

This extension is useful for understanding weighted resampling, but it should not be mistaken for the equal-probability bootstrap. In the uniform case, $p_i=1/n$ for every observation, and the expression reduces to the formula above.

Worked Example: Expected Coverage With Unequal Draw Probabilities

A hypothetical resampling procedure draws five records with replacement from four records. The per-draw probabilities are $0.40,\ 0.30,\ 0.20,$ and $0.10$, respectively. Find the inclusion probability for each record and the expected number of distinct records.

Method. For each record, calculate one minus the probability of missing it on all five draws. Then add the four inclusion probabilities. This is weighted resampling, not the usual uniform random forest bootstrap.

Record 1, with $p_1=0.40$:

P(1\text{ included})=1-(1-0.40)^5 =1-0.60^5 =1-0.07776 =0.92224.

Record 2, with $p_2=0.30$:

P(2\text{ included})=1-0.70^5 =1-0.16807 =0.83193.

Record 3, with $p_3=0.20$:

P(3\text{ included})=1-0.80^5 =1-0.32768 =0.67232.

Record 4, with $p_4=0.10$:

P(4\text{ included})=1-0.90^5 =1-0.59049 =0.40951.

Add the four inclusion probabilities:

$$ E[D]=0.92224+0.83193+0.67232+0.40951=2.83600. $$

The expected number of distinct records is 2.836. The probabilities of being omitted are $0.07776,\ 0.16807,\ 0.32768,$ and $0.59049$; these sum to $1.16400$, and $2.83600+1.16400=4$, as expected. A common error is to report $0.07776$ as record 1's inclusion probability. It is the omission probability; inclusion is its complement, $0.92224$.

From Omitted Records to OOB Predictions

Each tree in a forest has its own bootstrap sample. A record can be in bag for one tree and OOB for another. For a particular record and tree, the tree is eligible to provide an OOB prediction only if that record was omitted from the tree's bootstrap sample. The tree is fitted without that record's outcome, and then its predictors can be passed through the fitted tree to produce a prediction.

If $B$ trees are built from independently generated uniform bootstrap samples of size $m$, a particular observation's OOB indicator for each tree has probability $q=(1-1/n)^m$. Consequently, the expected number of trees that omit the observation is $Bq$. The probability that no tree omits it is $(1-q)^B$, because all $B$ samples must include it.

E[\text{OOB trees for a case}]=B\left(1-\frac{1}{n}\right)^m, \qquad P(\text{no OOB tree for the case}) =\left[1-\left(1-\frac{1}{n}\right)^m\right]^B.

A case-specific OOB prediction is formed from predictions made only by trees for which that case was OOB. For a regression illustration, those eligible tree predictions can be averaged. For classification, eligible trees can provide class predictions or class scores. The key point here is the eligibility rule: a tree that trained on a case is not an OOB predictor for that same case.

Worked Example: Selecting Eligible OOB Trees

A small hypothetical forest has four training records and six trees, each built from four draws with replacement. The bootstrap samples, shown as record labels with repeats retained, are:

\begin{aligned} T_1 &: (1,1,2,3), & T_2 &: (1,2,2,4),\\ T_3 &: (1,3,3,4), & T_4 &: (2,2,3,4),\\ T_5 &: (1,1,3,4), & T_6 &: (1,2,4,4). \end{aligned}

Find the trees eligible to produce an OOB prediction for record 2. If those trees predict a hypothetical cost of $14$ and $18$ thousand dollars, respectively, calculate the simple average of the eligible predictions.

Step 1: Check each sample for record 2. Record 2 appears in $T_1$, $T_2$, $T_4$, and $T_6$, so those trees are not eligible. It does not appear in $T_3=(1,3,3,4)$ or $T_5=(1,1,3,4)$, so those two trees are eligible.

Step 2: Combine the eligible predictions. The average is:

\frac{14+18}{2}=\frac{32}{2}=16

The illustrative OOB prediction is $16$ thousand dollars. Record 2's outcome must not be used to fit either eligible tree; only its predictor values are used to obtain the tree predictions. The calculation avoids including predictions from trees that had record 2 in their training samples.

Common Mistakes and Practical Interpretation

Reversing inclusion and omission. The expression $(1-1/n)^m$ is the probability of being omitted from every draw. The probability of inclusion is one minus that expression.
Equating sample size with distinct records. A bootstrap sample of $n$ draws contains $n$ draws, including repeats. It does not generally contain $n$ distinct observations.
Counting an OOB record as a separate data set. OOB status is specific to a record-tree pair. A record may be used to fit some trees and omitted from others.
Using every tree for a case's OOB prediction. Only trees whose bootstrap samples omitted that case are eligible. Including an in-bag tree would no longer follow the OOB construction.
Assuming every case has many eligible trees. With a finite number of trees, an observation can have few OOB trees or, by chance, none. Increasing the number of independently sampled trees reduces the chance of having none, but does not change the per-tree omission probability.

OOB predictions are possible because bootstrap sampling naturally leaves a portion of the training records out of each individual tree's sample. They provide a way to obtain predictions for a case from trees that did not use that case's outcome for fitting. The number of eligible trees varies by case, so the basic sampling calculation is also a useful check on whether the forest has generated adequate OOB coverage.

Check Your Understanding

For each problem, use the stated sample size and sampling scheme. Round probabilities to four decimal places where a decimal is requested.

A uniform bootstrap draws $10$ times with replacement from $10$ records. Find the OOB probability for one specified record and the expected number of distinct records. (Answer: OOB probability $0.3487$; expected distinct count $6.5132$.)
A tree is built from $m=6$ uniform draws from $n=12$ observations. Find the probability that a specified observation is omitted and the expected number of OOB observations in this one sample. (Answer: OOB probability $0.5933$; expected OOB count $12(11/12)^6\approx 7.1195$.)
A weighted resampling scheme makes four independent draws. Three records have per-draw probabilities $0.50,\ 0.25,$ and $0.25$. Find the expected number of distinct records. (Answer: $ [1-0.50^4]+2[1-0.75^4]=2.3047$.)
A forest has $80$ independently bootstrapped trees, each using $m=n=5$ uniform draws from five records. Find the expected number of trees that omit a specified record. (Answer: $80(4/5)^5=26.2144$ trees.)
For a particular case, three eligible OOB trees give regression predictions of $21,\ 24,$ and $27$ thousand dollars. A fourth tree included the case in its bootstrap sample and predicts $30$ thousand dollars. What is the simple average OOB prediction, and why is the fourth value excluded? (Answer: $24$ thousand dollars; exclude the fourth tree because the case was in its training sample.)

What You'll Learn