Bootstrap Sampling Versus Subsampling

Why the Sampling Scheme Matters

A random forest fits each tree using a sample of the training data. The familiar bootstrap scheme draws rows with replacement; subsampling draws rows without replacement. These choices affect more than how the training rows are assembled. They change how many distinct observations a tree can use, how many observations remain available for out-of-bag assessment, and how similar the training sets of different trees are likely to be.

The sample fraction needs to be interpreted in relation to the sampling scheme. For a bootstrap sample, it describes the number of draws relative to the training-set size. Repeated draws mean that this number is not the number of distinct rows. For a subsample without replacement, it describes the fraction of distinct rows selected. The two fractions therefore need not represent equivalent training sets.

In standard bootstrap aggregation, \(m=n\): each tree receives \(n\) draws, but some rows may be repeated and others omitted. In a subsample without replacement, selecting \(s=n\) would include every row and leave no out-of-bag observations. A smaller subsample, such as \(s=0.6n\), gives every row a chance to be excluded from a tree. The fraction is a choice to evaluate in context, not a universal rule that one method or fraction is always best.

Expected Coverage and Out-of-Bag Rows

For a bootstrap sample of size \(m\), the probability that a particular row is not selected on any draw is \((1-1/n)^m\). This gives the expected number of distinct rows in the sample and the expected number left out. For a subsample of \(s\) rows without replacement, exactly \(s\) rows are included and \(n-s\) are left out.

These are expectations for bootstrap sampling: the actual number of distinct rows in a particular bootstrap sample can be larger or smaller. In contrast, a fixed-size subsample without replacement always contains exactly \(s\) distinct rows. If the same procedure is repeated independently for \(B\) trees, the expected number of trees for which a particular row is OOB is \(B\) times its OOB probability. That number describes OOB availability; it does not itself guarantee a particular prediction quality.

Why the Bootstrap Has About 63.2% Distinct Rows

The commonly quoted coverage for a standard bootstrap follows directly from the probability of omission. Set \(m=n\). For a particular row, each of the \(n\) draws misses it with probability \(1-1/n\), so the probability of missing it on every draw is \((1-1/n)^n\). As \(n\) grows, this approaches \(e^{-1}\), approximately 0.3679. Thus the expected fraction of distinct rows included approaches \(1-e^{-1}\), approximately 0.6321.

This is an approximation for the expected coverage of a standard bootstrap, not a claim that every bootstrap sample contains exactly 63.2% of the rows. It also does not mean that a bootstrap tree is simply trained on a 63.2% subsample: the bootstrap has \(n\) draws, and repeated rows can contribute more than once to fitting the tree.

Subsample Fractions and OOB Availability

For a subsample without replacement, a fraction \(f\) of the training rows means \(s=fn\) selected rows when that product is an integer. The OOB fraction is exactly \(1-f\), and each row has that same probability of being OOB if the subset is chosen uniformly. If \(fn\) is not an integer, an implementation must use an integer sample size; the realized fraction is then based on that size.

Overlap, Tree Diversity, and Computation

The training samples of different trees overlap. One way to compare their expected overlap is to consider two independently sampled trees and count the rows included in both. If a row has probability \(p\) of appearing at least once in either tree's sample, its probability of appearing in both is \(p^2\). Summing across \(n\) rows gives expected overlap \(np^2\). For a uniform subsample of size \(s\), a row's inclusion probability is \(s/n\), so the expected overlap is \(s^2/n\).

This calculation concerns overlap in distinct rows, not the number of times a row is drawn. In a bootstrap tree, a selected row can appear multiple times and can therefore affect the fitted tree differently from a row included once. Lower expected overlap can create more opportunity for different trees to learn from different training rows, but it does not prove that the fitted trees will be less correlated or that the forest will predict better. Tree structure, predictor selection, signal strength, and the size of each tree's sample also matter.

Computational cost also depends on what is being compared. A standard bootstrap makes \(n\) draws per tree, whereas a subsample of \(s<n\) without replacement uses fewer training rows. A smaller subsample can reduce the work of fitting each tree, especially when many trees are required. However, total runtime depends on the software implementation and tree growth, so the reduction is not necessarily proportional to \(s/n\). A smaller sample also gives each tree less information, which can change its fitted structure and predictive performance. At a fixed nominal draw count, repeated bootstrap rows may reduce the number of distinct rows processed, but multiplicities still matter to the fitting procedure.

Choosing and Reporting a Sampling Scheme

A useful comparison keeps the setting clear: name whether sampling is with or without replacement, state the sample size or fraction, and say what that fraction counts. For example, “bootstrap, \(n\) draws with replacement” and “60% subsample without replacement” communicate different procedures. When fitting forests in R, packages expose these choices through implementation-specific arguments. In ranger, for example, the replace and sample.fraction arguments express the replacement rule and sampling fraction; set them explicitly and check the package's documentation for the version in use.

The OOB fraction is a practical consideration. A large subsample leaves fewer rows OOB per tree, while a smaller subsample leaves more. The standard bootstrap leaves about 36.8% of rows OOB in expectation for large \(n\), whereas a 60% subsample leaves exactly 40% OOB for each tree. Across a finite forest, a case receives OOB predictions only from trees that excluded it, so the number of available predictions can vary under bootstrap sampling. Avoid choosing a fraction solely to maximize OOB availability: the training information and resulting tree behavior matter as well.

Common Exam Traps

• Equating draws with distinct rows. A bootstrap of \(n\) draws can repeat rows. Its expected distinct-row count is less than \(n\).
• Using the subset formula for a bootstrap. The OOB fraction \(1-f\) applies to a fixed-size subsample without replacement, not to a bootstrap sample with \(fn\) draws.
• Calling expected coverage an exact count. The bootstrap's expected distinct-row fraction is about 63.2% for large \(n\), but any one sample can differ.
• Claiming that lower overlap guarantees better forests. Overlap describes training-row reuse; it does not determine prediction correlation or accuracy by itself.
• Assuming a smaller sample always means proportionally faster fitting. Runtime also depends on implementation and the tree-building work induced by the sample.