Bootstrap Sample Size And OOB Inclusion

Bootstrap Draws and Distinct Training Cases

A bootstrap sample is formed by drawing training cases with replacement. Its draw count is not necessarily the number of distinct cases it contains: the same case can appear several times, while another case may not be selected at all. This distinction matters in bagging because the draw count affects both the data available to fit each tree and the cases left out for that tree.

Let a training set contain \(n\) cases. Suppose one tree is fitted using \(m\) independent draws, each made uniformly from those \(n\) cases with replacement. A case is in-bag for this tree if it appears at least once in the \(m\) draws, and out-of-bag (OOB) if it does not appear. Here, \(m\) counts draws, including repeated selections; it does not count distinct cases.

These are expectations and probabilities, not guarantees for a particular bootstrap sample. For example, the expected number of distinct cases can be non-integer, even though every realized sample has an integer number of distinct cases. The formulas also assume that each draw is uniform over the same \(n\) cases. They do not apply unchanged if the resampling scheme gives different cases different selection probabilities.

Why the Inclusion Formula Holds

Consider one specified training case. On any one draw, the probability of selecting a different case is \(1-1/n\). For the specified case to be OOB, every one of the \(m\) draws must select a different case. Because the draws are independent, multiply the probability of omission across draws:

The in-bag probability is the complementary event, so it is \(1-(1-1/n)^m\). To obtain the expected count of distinct in-bag cases, define \(I_j=1\) if case \(j\) appears at least once and \(I_j=0\) otherwise. The distinct in-bag count is \(\sum_{j=1}^{n} I_j\). By linearity of expectation,

This reasoning does not require the indicators for different cases to be independent. They are not: selecting one case on a draw makes it slightly less likely that another case was selected on that same draw. Linearity of expectation is sufficient. Similarly, if \(J_j=1\) when case \(j\) is OOB and \(0\) otherwise, then the OOB count is \(\sum_{j=1}^{n}J_j\), with expectation \(n(1-1/n)^m\).

Changing the Number of Draws

For fixed \(n\), increasing \(m\) decreases the OOB probability \(q=(1-1/n)^m\), because \(0<1-1/n<1\) when \(n>1\). It therefore increases the probability that each case appears at least once and increases the expected distinct in-bag count. A larger draw count does not add new training cases; it gives more opportunities to select cases already in the fixed dataset.

When the conventional choice \(m=n\) is used, the OOB probability is \((1-1/n)^n\). For large \(n\), this is approximately \(e^{-1}\), or about \(0.3679\), and the expected in-bag fraction is about \(1-e^{-1}\), or \(0.6321\). These are large-\(n\) approximations, not exact values for every dataset. For example, with \(n=10\), the exact OOB fraction is \(0.9^{10}=0.3487\), not \(0.3679\).

More generally, if the draw count is approximately \(m=\alpha n\), where \(\alpha\) is a positive constant, then for large \(n\),

Thus using fewer than \(n\) draws tends to leave a larger fraction of cases out of each tree, while using more than \(n\) draws tends to leave a smaller fraction out. The approximation is useful for intuition; for a finite dataset, calculate the exact power when accuracy matters.

OOB Inclusion Across an Ensemble

OOB inclusion can refer to two different events: a case being OOB for one particular tree, or being OOB for at least one tree in an ensemble. Keep the events separate. Suppose \(B\) trees are built using independent bootstrap samples, each with \(m\) draws from the same \(n\) cases. For one fixed case, the probability of being OOB for a single tree is \(q=(1-1/n)^m\). The probability of being in-bag for that tree is \(1-q\). To be in-bag for every one of the \(B\) trees, the case must be in-bag \(B\) times, giving probability \((1-q)^B\). Therefore its probability of being OOB at least once is \(1-(1-q)^B\). The expected number of trees for which it is OOB is \(Bq\).

These ensemble formulas rely on independence of the bootstrap resamples across trees. They describe whether predictions could be formed for a case from trees that left it out; they do not calculate the resulting OOB prediction or its error. The number \(B\) affects how often a case is left out across the ensemble, while \(m\) determines the OOB probability for each individual tree.

Implications for Fitting Trees

Changing \(m\) changes the resampled training data for each tree. With fewer draws, the tree is built from fewer total selections and typically has fewer distinct cases available; repeated selections can still occur. This may make an individual tree more sensitive to the particular resample, depending on the splitting and stopping rules. It also increases the OOB probability per tree, so each case is eligible to be left out more often.

With more draws, the expected number of distinct in-bag cases increases, but it cannot exceed \(n\). The sample still contains only cases from the original training set, and the bootstrap can still repeat cases. As \(m\) becomes very large for fixed \(n\), the probability that any particular case is never drawn approaches zero, so OOB opportunities for that tree become scarce. These are structural consequences of the resampling scheme; they do not guarantee that predictive performance improves or worsens. Tree depth, minimum node size, the data, and other fitting choices also matter.

Increasing \(B\) is different from increasing \(m\). Increasing \(B\) supplies more independently resampled trees, while leaving the per-tree draw count unchanged. It can increase the chance that each training case is OOB for at least one tree, but it does not change the expected distinct in-bag count for any one tree. In particular, a small per-tree OOB probability can still produce useful coverage across many independent trees, although coverage should be checked rather than assumed.

Common Mistakes

A tempting shortcut is to assume that \(m\) draws select \(m\) different cases. For \(n=10\) and \(m=10\), that shortcut gives the wrong OOB fraction:

The incorrect calculation treats the sample as a selection without replacement. In a bootstrap sample, a case can be selected repeatedly, so ten draws need not cover ten distinct cases. The correct calculation tracks the probability of missing one specified case on every draw.

• Confusing draws with distinct cases. The bootstrap sample has \(m\) draws, but its number of unique cases is random.
• Calling \(q\) the in-bag probability. \(q=(1-1/n)^m\) is the OOB probability; the in-bag probability is \(1-q\).
• Using an approximation as an exact value. The \(e^{-1}\) approximation applies to \((1-1/n)^n\) for large \(n\), not to every finite sample size.
• Mixing up \(m\) and \(B\). \(m\) controls sampling within each tree; \(B\) controls the number of trees over which OOB opportunities accumulate.
• Treating expected counts as realized counts. An expected count such as \(6.5132\) describes an average over repeated resampling, not a fractional number of cases in one tree.