𝗪𝗵𝘆 𝗥𝗮𝗻𝗱𝗼𝗺 𝗙𝗼𝗿𝗲𝘀𝘁𝘀 𝗗𝗼𝗻’𝘁 𝗢𝘃𝗲𝗿𝗳𝗶𝘁 𝗮𝘀 𝗧𝗿𝗲𝗲𝘀 𝗚𝗿𝗼𝘄: 𝗨𝗻𝗱𝗲𝗿𝘀𝘁𝗮𝗻𝗱𝗶𝗻𝗴 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗶𝗻 𝘁𝗵𝗲 𝗥𝗮𝗻𝗱𝗼𝗺 𝗙𝗼𝗿𝗲𝘀𝘁 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺

Vinaitheerthan Renganathan

6 min read

·

Oct 23, 2026

--

Listen

Share

𝘈 𝘮𝘢𝘵𝘩𝘦𝘮𝘢𝘵𝘪𝘤𝘢𝘭 𝘢𝘯𝘥 𝘱𝘳𝘢𝘤𝘵𝘪𝘤𝘢𝘭 𝘨𝘶𝘪𝘥𝘦 𝘵𝘰 𝘓𝘦𝘰 𝘉𝘳𝘦𝘪𝘮𝘢𝘯’𝘴 𝘚𝘵𝘳𝘰𝘯𝘨 𝘓𝘢𝘸 𝘰𝘧 𝘓𝘢𝘳𝘨𝘦 𝘕𝘶𝘮𝘣𝘦𝘳𝘴 𝘱𝘳𝘰𝘰𝘧, 𝘵𝘩𝘦 𝘉𝘪𝘢𝘴-𝘝𝘢𝘳𝘪𝘢𝘯𝘤𝘦 𝘥𝘦𝘤𝘰𝘮𝘱𝘰𝘴𝘪𝘵𝘪𝗼𝘯, 𝘖𝘶𝘵-𝘰𝘧-𝘉𝘢𝘨 (𝘖𝘖𝘉) 𝘦𝘳𝘳𝘰𝘳 𝘴𝘵𝘢𝘣𝘪𝘭𝘪𝘻𝘢𝘵𝘪𝘰𝘯, 𝘢𝘯𝘥 𝘗𝘺𝘵𝘩𝘰𝘯 𝘪𝘮𝘱𝘭𝘦𝘮𝘦𝘯𝘵𝘢𝘵𝘪𝘰𝘯.

A single deep decision tree is notorious for high variance: left unconstrained, it memorizes training noise and generalizes poorly. Yet, combining hundreds of these unstable trees into a 𝗥𝗮𝗻𝗱𝗼𝗺 𝗙𝗼𝗿𝗲𝘀𝘁 produces an ensemble whose generalization error stabilizes rather than explodes as the number of trees approaches infinity.

Understanding 𝗰𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗶𝗻 𝘁𝗵𝗲 𝗥𝗮𝗻𝗱𝗼𝗺 𝗙𝗼𝗿𝗲𝘀𝘁 𝗮𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 requires distinguishing between two mathematical concepts: • 𝗘𝗻𝘀𝗲𝗺𝗯𝗹𝗲 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 (𝐵 → ∞): What happens to the generalization error as the number of trees 𝐵 increases for a fixed training dataset of size 𝑛. • 𝗦𝘁𝗮𝘁𝗶𝘀𝘁𝗶𝗰𝗮𝗹 𝗖𝗼𝗻𝘀𝗶𝘀𝘁𝗲𝗻𝗰𝘆 (𝑛 → ∞): Whether the Random Forest converges to the true underlying regression function or Bayes optimal classifier as the sample size 𝑛 grows to infinity.

This article breaks down the mathematics of Random Forest convergence, derives the variance-reduction limit, explains how to determine the optimal number of trees using Out-of-Bag (OOB) error, and demonstrates convergence empirically in Python.

━━━━━━━━━━━━━━━━━━━━

𝟭. 𝗔𝗿𝗰𝗵𝗶𝘁𝗲𝗰𝘁𝘂𝗿𝗲 𝗼𝗳 𝘁𝗵𝗲 𝗥𝗮𝗻𝗱𝗼𝗺 𝗙𝗼𝗿𝗲𝘀𝘁 𝗘𝗻𝘀𝗲𝗺𝗯𝗹𝗲

Given a training dataset 𝐷 = {(𝐱₁, 𝑦₁), …, (𝐱ₙ, 𝑦ₙ)} drawn independently and identically distributed (i.i.d.) from a joint distribution 𝑃(𝐗, 𝑌), a Random Forest constructs 𝐵 decision trees {ℎ(𝐱, Θ₁), …, ℎ(𝐱, Θ_𝐵)}.

Here, Θ_𝑏 represents an i.i.d. random vector governing two sources of stochasticity for the 𝑏-th tree:

1. 𝗕𝗼𝗼𝘁𝘀𝘁𝗿𝗮𝗽 𝗥𝗲𝘀𝗮𝗺𝗽𝗹𝗶𝗻𝗴 (𝗕𝗮𝗴𝗴𝗶𝗻𝗴): Selecting 𝑛 observations with replacement from 𝐷.
2. 𝗙𝗲𝗮𝘁𝘂𝗿𝗲 𝗦𝘂𝗯𝘀𝗽𝗮𝗰𝗶𝗻𝗴: Selecting a random subset of 𝑚_try ≤ 𝑝 features at each node split.

For regression, the ensemble prediction is the unweighted average across all 𝐵 trees, while for classification, it is the majority vote:

• 𝗥𝗲𝗴𝗿𝗲𝘀𝘀𝗶𝗼𝗻: 𝑓̂_𝐵(𝐱) = (1 / 𝐵) ∑{𝑏=1..𝐵} ℎ(𝐱, Θ_𝑏) • 𝗖𝗹𝗮𝘀𝘀𝗶𝗳𝗶𝗰𝗮𝘁𝗶𝗼𝗻: 𝐶̂_𝐵(𝐱) = arg max_𝑐 (1 / 𝐵) ∑{𝑏=1..𝐵} 𝕀(ℎ(𝐱, Θ_𝑏) = 𝑐)

━━━━━━━━━━━━━━━━━━━━

𝟮. 𝗕𝗿𝗲𝗶𝗺𝗮𝗻’𝘀 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗧𝗵𝗲𝗼𝗿𝗲𝗺 (𝗔𝘀 𝐵 → ∞)

In his seminal 2001 paper, Leo Breiman proved that Random Forests do not overfit as more trees are added. Instead, the generalization error converges almost surely to a finite limit.

𝗧𝗵𝗲 𝗠𝗮𝗿𝗴𝗶𝗻 𝗙𝘂𝗻𝗰𝘁𝗶𝗼𝗻 For a classification problem with true label 𝑌 and input vector 𝐗, define the 𝗺𝗮𝗿𝗴𝗶𝗻 𝗳𝘂𝗻𝗰𝘁𝗶𝗼𝗻 of a finite forest of 𝐵 trees as the difference between the proportion of votes for the correct class and the maximum proportion of votes for any incorrect class:

𝑚𝑟_𝐵(𝐗, 𝑌) = (1 / 𝐵) ∑ 𝕀(ℎ(𝐗, Θ_𝑏) = 𝑌) − max_{𝑗 ≠ 𝑌} (1 / 𝐵) ∑ 𝕀(ℎ(𝐗, Θ_𝑏) = 𝑗)

A positive margin (𝑚𝑟_𝐵(𝐗, 𝑌) > 0) indicates a correct classification, while a negative margin indicates a misclassification. The generalization error of the forest is the probability of a negative margin: 𝑃𝐸_𝐵* = 𝑃_{𝐗,𝑌}(𝑚𝑟_𝐵(𝐗, 𝑌) < 0).

𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗼𝗳 𝘁𝗵𝗲 𝗦𝘁𝗿𝗼𝗻𝗴 𝗟𝗮𝘄 𝗼𝗳 𝗟𝗮𝗿𝗴𝗲 𝗡𝘂𝗺𝗯𝗲𝗿𝘀 (𝗦𝗟𝗟𝗡) Because the random vectors Θ₁, Θ₂, …, Θ_𝐵 are conditionally i.i.d. given the training data 𝐷, the Strong Law of Large Numbers guarantees that as 𝐵 → ∞, the empirical average over trees converges almost surely (a.s.) to the expectation over the parameter space Θ:

lim_{𝐵→∞} 𝑃𝐸_𝐵* → 𝑃_{𝐗,𝑌}( 𝑃_Θ(ℎ(𝐗, Θ) = 𝑌) − max_{𝑗 ≠ 𝑌} 𝑃_Θ(ℎ(𝐗, Θ) = 𝑗) < 0 )

Furthermore, Breiman established an upper bound on this limiting generalization error 𝑃𝐸* in terms of two fundamental properties of the trees:

𝑃𝐸* ≤ ρ̄(1 − 𝑠²) / 𝑠²

• 𝗦𝘁𝗿𝗲𝗻𝗴𝘁𝗵 (𝑠): The expected margin across the distribution of (𝐗, 𝑌), measuring how accurate the individual trees are on average. • 𝗖𝗼𝗿𝗿𝗲𝗹𝗮𝘁𝗶𝗼𝗻 (ρ̄): The average correlation between the raw margin functions of two trees drawn with independent Θ and Θ′.

Lowering the correlation ρ̄ (via feature subspacing 𝑚_try) while maintaining high individual tree strength 𝑠 drives down the asymptotic error ceiling.

━━━━━━━━━━━━━━━━━━━━

𝟯. 𝗩𝗮𝗿𝗶𝗮𝗻𝗰𝗲 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗶𝗻 𝗥𝗲𝗴𝗿𝗲𝘀𝘀𝗶𝗼𝗻 𝗙𝗼𝗿𝗲𝘀𝘁𝘀

For regression, convergence is clearest through the variance of the ensemble average. Suppose each randomized tree has variance Var(ℎ(𝐱, Θ_𝑏)) = σ² and any pair of distinct trees has pairwise correlation ρ.

The variance of the ensemble prediction 𝑓̂_𝐵(𝐱) is:

Var(𝑓̂_𝐵(𝐱)) = ρσ² + ((1 − ρ) / 𝐵)σ²

Taking the limit as the number of trees approaches infinity (𝐵 → ∞):

1. 𝗧𝗵𝗲 𝘀𝗲𝗰𝗼𝗻𝗱 𝘁𝗲𝗿𝗺 ((1 − ρ) / 𝐵)σ² 𝘃𝗮𝗻𝗶𝘀𝗵𝗲𝘀 𝘁𝗼 𝟬 at a Monte Carlo rate of 𝒪(1 / 𝐵). This represents the algorithmic variance injected by bootstrap sampling and random feature splits.
2. 𝗧𝗵𝗲 𝗳𝗶𝗿𝘀𝘁 𝘁𝗲𝗿𝗺 ρσ² 𝗿𝗲𝗺𝗮𝗶𝗻𝘀 𝗰𝗼𝗻𝘀𝘁𝗮𝗻𝘁 regardless of how many trees are added. This is the irreducible ensemble variance governed by tree correlation ρ and training sample size 𝑛.

𝗦𝘂𝗺𝗺𝗮𝗿𝘆 𝗼𝗳 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗥𝗲𝗴𝗶𝗺𝗲𝘀: • 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝗶𝗰 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 (𝐵 → ∞, 𝗳𝗶𝘅𝗲𝗱 𝑛): Driven by the Strong Law of Large Numbers over Θ. Adding trees stabilizes predictions at rate 𝒪(1/𝐵) and never causes iterative overfitting. • 𝗩𝗮𝗿𝗶𝗮𝗻𝗰𝗲 𝗙𝗹𝗼𝗼𝗿 (lim_{𝐵→∞} Var = ρσ²): Driven by pairwise tree correlation ρ controlled by 𝑚_try. Adding more trees cannot eliminate correlation between trees; tuning 𝑚_try is required. • 𝗦𝘁𝗮𝘁𝗶𝘀𝘁𝗶𝗰𝗮𝗹 𝗖𝗼𝗻𝘀𝗶𝘀𝘁𝗲𝗻𝗰𝘆 (𝑛 → ∞, 𝐿² 𝗕𝗮𝘆𝗲𝘀 𝗥𝗶𝘀𝗸): Requires leaf size 𝑘_𝑛 → ∞ and 𝑘_𝑛 / 𝑛 → 0 (Scornet et al., 2015). Unpruned trees can still overfit noisy datasets unless tree depth or leaf size is regularized.

━━━━━━━━━━━━━━━━━━━━

𝟰. 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝗶𝗰 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝘃𝘀. 𝗦𝘁𝗮𝘁𝗶𝘀𝘁𝗶𝗰𝗮𝗹 𝗖𝗼𝗻𝘀𝗶𝘀𝘁𝗲𝗻𝗰𝘆 (𝐵 → ∞ 𝘃𝘀. 𝑛 → ∞)

A common misconception is that “Random Forests cannot overfit.” Mathematically, adding more trees (𝐵 → ∞) does not cause overfitting, unlike boosting algorithms (such as AdaBoost or Gradient Boosting) where excessive iterations degrade test error.

However, the limiting infinite forest (𝐵 = ∞) trained on a noisy dataset of size 𝑛 𝗰𝗮𝗻 𝘀𝘁𝗶𝗹𝗹 𝗼𝘃𝗲𝗿𝗳𝗶𝘁 𝘁𝗵𝗲 𝗱𝗮𝘁𝗮𝘀𝗲𝘁 𝗶𝘁𝘀𝗲𝗹𝗳 if the individual trees are grown to full depth (𝚖𝚒𝚗_𝚜𝚊𝚖𝚙𝚕𝚎𝚜_𝚕𝚎𝚊𝚏 = 1). As demonstrated by Biau (2012) and Scornet, Biau, and Vert (2015), achieving 𝐿² 𝘀𝘁𝗮𝘁𝗶𝘀𝘁𝗶𝗰𝗮𝗹 𝗰𝗼𝗻𝘀𝗶𝘀𝘁𝗲𝗻𝗰𝘆 (converging to the true regression function 𝑓(𝐱) = 𝔼[𝑌 ∣ 𝐗 = 𝐱] as 𝑛 → ∞) requires controlling tree complexity so that the number of terminal nodes grows slower than the sample size 𝑛.

━━━━━━━━━━━━━━━━━━━━

𝟱. 𝗠𝗼𝗻𝗶𝘁𝗼𝗿𝗶𝗻𝗴 𝗖𝗼𝗻𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲 𝗶𝗻 𝗣𝗿𝗮𝗰𝘁𝗶𝗰𝗲 𝘃𝗶𝗮 𝗢𝘂𝘁-𝗼𝗳-𝗕𝗮𝗴 (𝗢𝗢𝗕) 𝗘𝗿𝗿𝗼𝗿

Because each bootstrap sample draws 𝑛 observations with replacement, the probability that a specific observation 𝑖 is excluded from a given tree 𝑏 is:

𝑃(𝑖 ∉ Bootstrap_𝑏) = (1 − 1 / 𝑛)ⁿ → 𝑒⁻¹ ≈ 0.3679 (as 𝑛 → ∞)

Roughly 𝟯𝟲.𝟴% of the training instances are left out of each tree. By aggregating predictions for each point 𝑖 exclusively across the trees where 𝑖 was Out-of-Bag, the OOB error curve provides an unbiased, cross-validated trajectory of ensemble convergence without requiring a separate validation split.

𝗣𝘆𝘁𝗵𝗼𝗻 𝗜𝗺𝗽𝗹𝗲𝗺𝗲𝗻𝘁𝗮𝘁𝗶𝗼𝗻: 𝗧𝗿𝗮𝗰𝗸𝗶𝗻𝗴 𝗢𝗢𝗕 𝗘𝗿𝗿𝗼𝗿 𝗦𝘁𝗮𝗯𝗶𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻 Using warm_start=True in scikit-learn allows incremental tree additions to inspect the exact point where the OOB error plateaus:

Python

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier

# 1. Generate synthetic classification dataset
X, y = make_classification(
    n_samples=2000, n_features=25, n_informative=15,
    n_redundant=5, flip_y=0.1, random_state=42
)# 2. Initialize Random Forest with warm_start=True and oob_score=True
rf = RandomForestClassifier(
    warm_start=True,
    oob_score=True,
    max_features="sqrt",
    random_state=42,
    n_jobs=-1
)# 3. Track OOB error across increasing ensemble sizes B
tree_steps = range(10, 501, 10)
oob_errors = []for n_trees in tree_steps:
    rf.set_params(n_estimators=n_trees)
    rf.fit(X, y)
    oob_error = 1.0 - rf.oob_score_
    oob_errors.append(oob_error)# 4. Identify empirical convergence point (where step change < tol)
diffs = np.abs(np.diff(oob_errors))
converged_idx = np.where(diffs < 0.0005)[0][0]
print(f"OOB Error at B=10   : {oob_errors[0]:.4f}")
print(f"OOB Error at B=500  : {oob_errors[-1]:.4f}")
print(f"Stabilization Point : ~{list(tree_steps)[converged_idx]} trees")

━━━━━━━━━━━━━━━━━━━━

𝟲. 𝗣𝗿𝗮𝗰𝘁𝗶𝗰𝗮𝗹 𝗚𝘂𝗶𝗱𝗲𝗹𝗶𝗻𝗲𝘀 𝗳𝗼𝗿 𝗛𝘆𝗽𝗲𝗿𝗽𝗮𝗿𝗮𝗺𝗲𝘁𝗲𝗿 𝗧𝘂𝗻𝗶𝗻𝗴

• 𝗦𝗲𝘁𝘁𝗶𝗻𝗴 n_estimators (𝐵): Because error decreases at rate 𝒪(1 / 𝐵), returns diminish rapidly past 200–500 trees. Choose 𝐵 where the OOB error variance flattens out.
• 𝗟𝗼𝘄𝗲𝗿𝗶𝗻𝗴 𝘁𝗵𝗲 𝗔𝘀𝘆𝗺𝗽𝘁𝗼𝘁𝗶𝗰 𝗙𝗹𝗼𝗼𝗿 𝘃𝗶𝗮 max_features (𝑚_try): If the OOB curve plateaus at an unacceptably high error, adding more trees will not help. Tune max_features (to reduce tree correlation ρ) and min_samples_leaf (to prevent individual trees from fitting noise).
• 𝗖𝗹𝗮𝘀𝘀 𝗜𝗺𝗯𝗮𝗹𝗮𝗻𝗰𝗲 𝗮𝗻𝗱 𝗥𝗮𝗿𝗲 𝗘𝘃𝗲𝗻𝘁𝘀: When predicting rare probabilities, require a larger 𝐵 so that every minority-class sample receives a sufficient number of Out-of-Bag evaluations (typically 𝐵 ≥ 500).