Tree Dependence and Aggregation Variance

Why the Covariance Between Trees Matters

A forest prediction averages predictions from several trees. If those predictions were independent and had the same variance, averaging $B$ of them would divide their variance by $B$. But trees grown on the same data, or with overlapping subsamples and similar randomization, need not be independent. The covariance between tree predictions then contributes directly to the variance of their average.

We will study variance at a fixed feature value $x$. Write $\mathcal D$ for the observed training data, and let $T_b(x)$ be the prediction from tree $b$. Conditional on $\mathcal D$, these predictions can still be random because of any randomization used to construct the trees. The calculations below concern that specified source of randomness. All conditional variances and covariances are assumed finite.

Definition: The average of $B$ tree predictions at $x$ is $\bar T_B(x)=B^{-1}\sum_{b=1}^B T_b(x)$. Conditional on the training data, write $v_b(x)=\operatorname{Var}(T_b(x)\mid\mathcal D)$ for the variance of tree $b$, and $c_{ij}(x)=\operatorname{Cov}(T_i(x),T_j(x)\mid\mathcal D)$ for the covariance between trees $i$ and $j$.

The tree count $B$ is not itself a measure of how much independent information an ensemble contains. The variance depends both on the individual tree variances and on how predictions move together. In particular, an additional tree reduces the contribution from individual-tree variability only to the extent that its prediction is not fully redundant with the existing predictions.

The General Variance Identity

No exchangeability or equal-variance assumption is needed for the basic formula. Each pair of trees can have its own covariance.

Theorem: For $B$ tree predictions with finite conditional second moments, $$ \operatorname{Var}(\bar T_B(x)\mid\mathcal D) = \frac{1}{B^2} \left\{ \sum_{b=1}^B v_b(x) + 2\sum_{1\le i<j\le B}c_{ij}(x) \right\}. $$

To prove the identity, set $S=\sum_{b=1}^B T_b(x)$. Expanding the conditional variance of this sum gives

\begin{aligned} \operatorname{Var}(S\mid\mathcal D) &= E\left[ \left\{\sum_{b=1}^B \bigl(T_b(x)-E[T_b(x)\mid\mathcal D]\bigr)\right\}^2 \middle|\mathcal D \right]\\ &= \sum_{b=1}^B E\left[ \bigl(T_b(x)-E[T_b(x)\mid\mathcal D]\bigr)^2 \middle|\mathcal D\right]\\ &\quad+ 2\sum_{1\le i<j\le B} E\left[ \bigl(T_i(x)-E[T_i(x)\mid\mathcal D]\bigr) \bigl(T_j(x)-E[T_j(x)\mid\mathcal D]\bigr) \middle|\mathcal D\right]\\ &= \sum_{b=1}^B v_b(x)+2\sum_{1\le i<j\le B}c_{ij}(x). \end{aligned}

Since $\bar T_B(x)=S/B$, scaling a random variable by $1/B$ scales its variance by $1/B^2$. This proves the result. $\square$

The factor of two appears because each off-diagonal covariance occurs twice in the expansion: once for the ordered pair $(i,j)$, and once for $(j,i)$. Equivalently, one can sum over all ordered pairs, including the diagonal variances, without the factor of two.

Worked Example: Unequal Tree Variances and Covariances

Suppose three tree predictions at a fixed $x$, conditional on $\mathcal D$, each have variance $4$, and every distinct pair has covariance $1$. Calculate the variance of their average.

There are three variance terms, so their total is $3(4)=12$. There are three distinct pairs, each with covariance $1$; the covariance contribution is $2(3)(1)=6$. Thus

\operatorname{Var}(\bar T_3(x)\mid\mathcal D) =\frac{12+6}{3^2}=2.

If the three predictions were independent but retained the same individual variance, their average would instead have variance $12/9=4/3$. The difference, $2/3$, is exactly the covariance contribution $6/9$. The calculation makes clear why knowing the variance of an individual tree is not enough.

Exchangeable Trees and the Covariance Floor

A useful special case is an exchangeable collection, meaning that, conditional on $\mathcal D$, the joint distribution is unchanged by permuting the tree indices. It follows that all tree predictions have the same variance $v(x)$ and every distinct pair has the same covariance $c(x)$. The exact variance identity then simplifies to a formula that exposes the effect of dependence.

Theorem: If $B$ tree predictions are exchangeable conditional on $\mathcal D$, have finite second moments, common variance $v(x)$, and common pairwise covariance $c(x)$, then $$ \operatorname{Var}(\bar T_B(x)\mid\mathcal D) = \frac{v(x)}{B}+\frac{B-1}{B}c(x). $$ If $v(x)$ and $c(x)$ do not change as $B$ increases and $c(x)>0$, this variance converges to $c(x)$, not to zero at a one-over-$B$ rate.

For the derivation, there are $B$ diagonal variance terms and $B(B-1)/2$ distinct pairs. Substitution into the general identity gives

\begin{aligned} \operatorname{Var}(\bar T_B(x)\mid\mathcal D) &=\frac{Bv(x)+2\{B(B-1)/2\}c(x)}{B^2}\\ &=\frac{v(x)}{B}+\frac{B-1}{B}c(x). \end{aligned}

With fixed $v(x)$ and $c(x)$, the first term tends to zero and the coefficient $(B-1)/B$ tends to one. Therefore the variance tends to $c(x)$. This is a covariance floor: averaging removes the part of the variation specific to individual trees but leaves the shared part. $\square$

When $v(x)>0$, define the common pairwise correlation by $\rho(x)=c(x)/v(x)$. The same expression can be written

\operatorname{Var}(\bar T_B(x)\mid\mathcal D) =v(x)\left\{\rho(x)+\frac{1-\rho(x)}{B}\right\}.

This parameterization is valid when the trees have positive variance. It is also a reminder that exchangeability is an assumption, not an automatic property of every forest. When variances or pairwise covariances differ, use the general identity rather than substituting an average correlation without justification.

Worked Example: A Shared Random Component Creates a Floor

Let $U\sim N(0,3)$ and let $\epsilon_1,\ldots,\epsilon_B$ be independent $N(0,1)$ random variables, also independent of $U$. Suppose $T_b(x)=U+\epsilon_b$. Find the variance of the average and its limit as $B$ increases.

Each tree has mean zero and variance $\operatorname{Var}(U)+\operatorname{Var}(\epsilon_b)=3+1=4$. For two distinct trees, independence of the separate $\epsilon$'s and of $U$ gives

\operatorname{Cov}(T_i(x),T_j(x)) =\operatorname{Cov}(U+\epsilon_i,U+\epsilon_j) =\operatorname{Var}(U)=3.

The exchangeable formula therefore gives

\operatorname{Var}(\bar T_B(x)) =\frac{4}{B}+\frac{B-1}{B}(3) =3+\frac{1}{B}.

For $B=4$, the variance is $3+1/4=3.25$, while each tree has variance $4$. As $B$ grows, the variance tends to $3$. Averaging reduces the contribution of the independent $\epsilon_b$'s, but it cannot average away the shared random component $U$.

A positive covariance floor is a precise reason that “more trees” does not always imply a one-over-tree-count variance rate. More generally, if $v$ is fixed and the common covariance depends on $B$, the formula is $v/B+(B-1)c_B/B$. A one-over-$B$ rate can hold if $c_B$ is itself sufficiently small, for example if $c_B=O(1/B)$; it does not follow from averaging alone.

Dependence Can Also Be Negative

Covariances are not necessarily positive. Negative dependence can reduce the variance of an average more than an independence calculation would suggest. The covariance matrix must still be positive semidefinite, so the covariances cannot be chosen arbitrarily. For example, in the exchangeable equal-variance case with $B>1$, the variance formula must be nonnegative, which requires $c(x)\ge -v(x)/(B-1)$.

Worked Example: Negative Covariance Cancels the Average

Let $Z_1,\ldots,Z_B$ be independent $N(0,1)$ random variables, define $\bar Z=B^{-1}\sum_{b=1}^B Z_b$, and set $T_b(x)=Z_b-\bar Z$. Calculate the individual variances, the pairwise covariances, and the variance of the average prediction.

Since $\operatorname{Var}(\bar Z)=1/B$ and $\operatorname{Cov}(Z_b,\bar Z)=1/B$,

\operatorname{Var}(T_b(x)) =1+\frac{1}{B}-2\frac{1}{B} =1-\frac{1}{B}.

For $i\ne j$, $\operatorname{Cov}(Z_i,Z_j)=0$, while $\operatorname{Cov}(Z_i,\bar Z)=\operatorname{Cov}(Z_j,\bar Z)=1/B$. Hence

\operatorname{Cov}(T_i(x),T_j(x)) =0-\frac{1}{B}-\frac{1}{B}+\frac{1}{B} =-\frac{1}{B}.

The average prediction is identically zero because

\bar T_B(x)=\frac{1}{B}\sum_{b=1}^B(Z_b-\bar Z) =\bar Z-\bar Z=0.

Its variance is therefore zero. The exchangeable formula confirms this:

\frac{1-1/B}{B}+\frac{B-1}{B}\left(-\frac{1}{B}\right)=0.

For $B=4$, each prediction has variance $3/4$ and each pair has covariance $-1/4$. Their average has zero variance, not because the trees are individually constant, but because their deviations cancel exactly.

Conditional and Unconditional Variance

Conditioning on $\mathcal D$ isolates the variation due to the tree randomization specified in the analysis. If the training data are themselves viewed as random, the unconditional variance also includes variation in the conditional mean across data sets. For any square-integrable random variable $W$,

\operatorname{Var}(W) =E[\operatorname{Var}(W\mid\mathcal D)] +\operatorname{Var}(E[W\mid\mathcal D]).

This identity follows by writing $W-E[W]=(W-E[W\mid\mathcal D])+(E[W\mid\mathcal D]-E[W])$, squaring, and taking expectations. The cross term is zero because

E[W-E[W\mid\mathcal D]\mid\mathcal D]=0.

Thus conditional aggregation variance alone is not automatically the full sampling variance of a forest predictor. The second term records how the conditional mean prediction varies over possible training data sets. Keeping the two sources separate avoids attributing all variability to tree-to-tree dependence.

Common Mistake and Practical Interpretation

A common mistake is to calculate an individual tree variance $v$, divide it by $B$, and report that as the variance of the forest average. That calculation silently assumes the covariance terms are all zero. The correction is to write the general identity first, then justify independence or another dependence structure before simplifying. If trees are conditionally independent with common variance $v$, the covariance terms vanish and the variance is $v/B$. If exchangeable trees have positive covariance $c$, the result is $v/B+(B-1)c/B$.

In applications, the covariance contribution explains why highly similar trees can provide less variance reduction than their count suggests. It does not, by itself, determine prediction risk: bias and the target of the prediction also matter. The useful conclusion here is narrower and exact: the variance of an average is controlled by both the marginal tree variability and the dependence among tree predictions.

Key takeaway: For an average of dependent trees, sum the individual variances and all pairwise covariance contributions, then divide by $B^2$. Under exchangeability, a fixed positive pairwise covariance leaves a nonzero variance floor as the number of trees grows.

Check Your Understanding

Answer each question by identifying the assumptions you use.

Write the conditional variance formula for an average of four tree predictions when their variances and pairwise covariances may differ.
For exchangeable trees with variance $v$ and covariance $c$, what is the variance of their average, and what does it approach if $c>0$ is fixed?
Why is dividing a single-tree variance by the number of trees unjustified when the predictions are dependent?
In the shared-component example, which part of each prediction is reduced by averaging, and which part remains?
Can negative pairwise covariance make the variance of an average smaller than under independence? Give the condition that keeps the exchangeable variance nonnegative.