Monte Carlo Error in Finite Forests

What the Finite Forest Approximates

A randomized forest prediction depends on two sources of randomness: the observed training data and the random choices made when constructing trees. These choices may include subsampling, feature selection, and split selection. Once the training data and a query point are held fixed, a finite forest averages a finite number of randomized tree predictions. The corresponding infinite-forest prediction averages over the tree-construction randomness itself.

This tutorial quantifies the gap between those two predictions. The gap is Monte Carlo error: it arises because only finitely many randomized trees are used to approximate an expectation. It is not, by itself, a measure of how well the forest estimates the regression function or predicts new responses. Those statistical errors involve additional randomness and targets.

Definition: Let \(\mathcal G\) denote the information held fixed for the calculation, including the training data and the query point \(x\). Let \(T(x)\) be the prediction from one randomized tree. The infinite-forest prediction at \(x\) is \(\mu(x)=E[T(x)\mid\mathcal G]\), provided this conditional expectation exists. For \(B\) randomized trees with predictions \(T_1(x),\ldots,T_B(x)\), the finite-forest prediction is \(\hat\mu_B(x)=B^{-1}\sum_{b=1}^{B}T_b(x)\).

The key comparison is conditional on \(\mathcal G\): after fixing the training sample and the query point, the only randomness left in \(\hat\mu_B(x)-\mu(x)\) is the randomness used to generate the trees. To obtain the usual \(1/B\) variance reduction, the \(B\) tree predictions must be conditionally independent draws from the same tree-randomization distribution. Assume also that \(E[T(x)^2\mid\mathcal G]\) is finite. These conditions are stated at a fixed query point; a statement for one \(x\) does not automatically give a uniform guarantee over all query points.

Exact Conditional Monte Carlo Error

Write \(v(x)=\operatorname{Var}(T(x)\mid\mathcal G)\). The finite-tree average is conditionally unbiased for the infinite-forest prediction, and its conditional variance is exactly \(v(x)/B\). This identity is the basic Monte Carlo error calculation for a finite forest.

Theorem: Suppose, conditional on \(\mathcal G\), \(T_1(x),\ldots,T_B(x)\) are independent and identically distributed, with conditional mean \(\mu(x)\) and finite conditional variance \(v(x)\). Then \[ E[\hat\mu_B(x)-\mu(x)\mid\mathcal G]=0,\qquad E[(\hat\mu_B(x)-\mu(x))^2\mid\mathcal G] =\operatorname{Var}(\hat\mu_B(x)\mid\mathcal G) =\frac{v(x)}{B}. \] Consequently, for every \(\varepsilon>0\), \[ P\bigl(|\hat\mu_B(x)-\mu(x)|\geq\varepsilon\mid\mathcal G\bigr) \leq \frac{v(x)}{B\varepsilon^2}. \]

Proof. Conditional on \(\mathcal G\), each tree prediction has mean \(\mu(x)\). Linearity of conditional expectation therefore gives \(E[\hat\mu_B(x)\mid\mathcal G]=B^{-1}\sum_{b=1}^{B}\mu(x)=\mu(x)\). For the variance, conditional independence makes each cross-covariance zero, so

\operatorname{Var}(\hat\mu_B(x)\mid\mathcal G) =\operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^{B}T_b(x)\middle|\mathcal G\right) =\frac{1}{B^2}\sum_{b=1}^{B}\operatorname{Var}(T_b(x)\mid\mathcal G) =\frac{v(x)}{B}.

Since the conditional mean of the difference is zero, its conditional mean squared value equals its conditional variance. Apply conditional Chebyshev's inequality to that difference to obtain the displayed probability bound. \(\square\)

The equality gives a root-mean-square error of \(\sqrt{v(x)/B}\), conditional on the training data and query point. The probability bound is a guarantee, not generally an exact probability: Chebyshev's inequality can be conservative, especially when the tree-prediction distribution has additional structure. If \(v(x)\) is known to be at most a constant \(C\), the bound becomes \(C/(B\varepsilon^2)\). Increasing the number of trees reduces this Monte Carlo component at rate \(1/B\) in mean squared error, or \(1/\sqrt B\) in root-mean-square error.

Worked Example: Bernoulli Tree Predictions

Fix the training data and a query point. Suppose one tree predicts \(1\) with probability \(0.3\) and \(0\) with probability \(0.7\). For \(B=25\) conditionally independent trees, calculate the infinite-forest prediction, the finite-forest mean squared error, and the Chebyshev bound for an error of at least \(0.2\).

The infinite-forest prediction is the conditional mean: \(\mu(x)=1(0.3)+0(0.7)=0.3\). For a Bernoulli random variable with success probability \(0.3\), the conditional variance is \(v(x)=0.3(1-0.3)=0.21\).

The exact conditional mean squared error of the 25-tree average is therefore \(0.21/25=0.0084\). Its conditional root-mean-square error is \(\sqrt{0.0084}\approx 0.0917\). For \(\varepsilon=0.2\), the theorem gives

P\bigl(|\hat\mu_{25}(x)-0.3|\geq 0.2\mid\mathcal G\bigr) \leq \frac{0.21}{25(0.2)^2} =\frac{0.21}{1} =0.21.

Thus the squared-error calculation is exact, while \(0.21\) is an upper bound on the stated tail probability. The calculation concerns variation in the 25 randomized tree predictions after conditioning; it says nothing on its own about whether \(0.3\) is close to the true conditional response mean.

When Bounded Tree Predictions Give a Uniform Variance Bound

Often the conditional variance \(v(x)\) is not calculated directly. A known range for the tree predictions gives a general bound instead. In regression, if every prediction is an average of responses known to lie in \([a,b]\), then every tree prediction also lies in that interval. The following result converts this range restriction into a bound on finite-forest Monte Carlo error.

Theorem: Under the conditional independence and identical-distribution assumptions above, suppose that, conditional on \(\mathcal G\), \(a\leq T(x)\leq b\) almost surely, where \(a\) and \(b\) are fixed given \(\mathcal G\). Then \[ \operatorname{Var}(\hat\mu_B(x)\mid\mathcal G) \leq \frac{(b-a)^2}{4B}, \qquad P\bigl(|\hat\mu_B(x)-\mu(x)|\geq\varepsilon\mid\mathcal G\bigr) \leq \frac{(b-a)^2}{4B\varepsilon^2}. \]

Derivation. Set \(m=E[T(x)\mid\mathcal G]\). Because \(a\leq T(x)\leq b\), the product \((T(x)-a)(b-T(x))\) is nonnegative. Taking its conditional expectation and expanding gives

0\leq E[(T(x)-a)(b-T(x))\mid\mathcal G] =(a+b)m-ab-E[T(x)^2\mid\mathcal G].

Rearranging and subtracting \(m^2\) yields

\operatorname{Var}(T(x)\mid\mathcal G) =E[T(x)^2\mid\mathcal G]-m^2 \leq (b-m)(m-a) \leq \frac{(b-a)^2}{4}.

For the last inequality, \((b-m)(m-a)\leq (b-a)^2/4\) follows by expanding \(\bigl(m-(a+b)/2\bigr)^2\geq 0\). Apply the exact variance identity from the preceding theorem, then its Chebyshev bound, to obtain both claims. \(\square\)

Worked Example: Predictions Between Zero and Ten

Suppose, conditional on the training data and query point, each tree prediction lies between \(0\) and \(10\). Find a bound on the mean squared Monte Carlo error for \(B=100\), and an upper bound on the probability that the finite forest differs from the infinite forest by at least \(1\).

Here \(a=0\), \(b=10\), and \((b-a)^2/4=100/4=25\). The conditional variance of the 100-tree average is at most \(25/100=0.25\). Its conditional mean squared error is the same as its conditional variance because the average is conditionally unbiased. The root-mean-square error is therefore at most \(\sqrt{0.25}=0.5\).

For a discrepancy of at least \(1\), Chebyshev's inequality gives

P\bigl(|\hat\mu_{100}(x)-\mu(x)|\geq 1\mid\mathcal G\bigr) \leq \frac{25}{100(1)^2}=0.25.

This bound uses only the prediction range; the actual conditional variance may be smaller. The conclusion also depends on independently randomized tree draws given \(\mathcal G\), not merely on each prediction lying between \(0\) and \(10\).

The Query Point and the Conditioning Matter

The variance \(v(x)\) is specific to the query point and to the information conditioned upon. A fixed-\(x\) statement means that the same \(x\) is supplied to every tree and to the infinite forest, while the tree randomizations are drawn from their common conditional law. If the query point is random, one can condition on its value as part of \(\mathcal G\), provided it is chosen without introducing dependence between the query and the tree randomizations. The bound then applies conditionally at that realized point.

A pointwise result should not be silently interpreted as a guarantee for every point in a continuum. For a finite collection of \(q\) fixed query points, if the conditional variance at each is at most \(C\), the union bound gives \(P(\max_{1\leq j\leq q}|\hat\mu_B(x_j)-\mu(x_j)|\geq\varepsilon\mid\mathcal G) \leq qC/(B\varepsilon^2)\). This follows by adding the \(q\) individual probability bounds; independence across query points is not required. The factor \(q\) shows why a pointwise guarantee alone does not supply a uniform guarantee over a large set.

Worked Example: A Random Query With Different Variances

Fix the training data. A query \(X\) equals \(a\) with probability \(0.2\) and \(b\) with probability \(0.8\), and it is selected independently of the tree randomizations. At \(a\), a tree predicts \(0\) or \(1\) with equal probabilities. At \(b\), every tree predicts \(3\). For \(B=10\), calculate the conditional mean squared Monte Carlo error at each query and its average over \(X\).

At \(a\), the infinite-forest prediction is \(0.5\), and the single-tree variance is \(0.5(0-0.5)^2+0.5(1-0.5)^2=0.25\). Thus the conditional mean squared error of the 10-tree average is \(0.25/10=0.025\).

At \(b\), each tree predicts \(3\) with probability one. Its variance, and consequently the finite-forest mean squared error, are both zero. Averaging these conditional errors over the query distribution gives

E[(\hat\mu_{10}(X)-\mu(X))^2\mid\text{training data}] =0.2(0.025)+0.8(0)=0.005.

This average error is not the fixed-point error at \(a\): it incorporates the chance of querying the lower-variance point \(b\). To state a guarantee for a particular realized query, condition on that query value and use its own tree-prediction variance.

Common Mistakes and Interpretation

Calling Monte Carlo error total prediction error. The bound compares a finite randomized forest with its infinite-tree conditional expectation. It does not bound the distance from either predictor to the true regression function.
Using the \(1/B\) variance formula without conditional independence. If all trees share a random seed so that \(T_b(x)=Z(x)\) for every \(b\), then \(\hat\mu_B(x)=Z(x)\) for every \(B\). Its conditional variance is \(\operatorname{Var}(Z(x)\mid\mathcal G)\), not that variance divided by \(B\). More generally, dependent tree draws require their covariance terms in the variance of the average.
Confusing the variance bound with a tail probability equal to that bound. Chebyshev gives an inequality, not an exact probability. It can be loose, and a right-hand side above \(1\) is still only a valid but uninformative upper bound.
Dropping the query-point condition. The conditional variance can change with \(x\). A bound verified at one point does not automatically apply to all points or to a random query without accounting for its distribution.

Key takeaway: At a fixed query point, condition on the training data and generate \(B\) independent, identically distributed randomized trees. The finite forest is conditionally unbiased for the infinite forest, with exact Monte Carlo mean squared error \(\operatorname{Var}(T(x)\mid\mathcal G)/B\). The validity of this calculation depends on what is held fixed and how the trees are randomized.

Check Your Understanding

Use the conditional Monte Carlo framework to answer these questions.

State the assumptions that make the conditional variance of a \(B\)-tree average equal to the single-tree conditional variance divided by \(B\).
If the conditional single-tree variance at a fixed point is \(0.8\) and \(B=20\), what is the exact conditional mean squared Monte Carlo error?
Why does a bound on the finite forest's distance from the infinite forest not, by itself, bound its prediction error relative to the true regression function?
If all trees use the same random seed and therefore return identical predictions, what happens to the variance of their average as \(B\) increases?
For a random query point, what additional conditioning makes the fixed-point variance calculation applicable?