# Why does the correlation between decision trees have to be positive?

In the book "Elements of statistical learning" we have that the variance of a the random forest is given by

$$V(\frac{1}{n} \sum X_i)= \rho \sigma^2+ \frac{1-\rho}{n}\sigma^2$$

where $$\rho$$ is the pairwise correlation between all $$n$$ trees which all have variance $$\sigma^2$$. It is stated that $$\rho\geq 0$$ otherwise the proof fails. I know that $$\rho\geq -1/(n-1)$$ but that does not imply that $$\rho>0$$? Say we have $$n=3$$ we have that $$\rho$$ can take the values $$-0.5$$ without violating anything. How come the proof is only for $$\rho\geq 0$$?

• Try substituting any negative number (well, between $-1$ and $0$) for $\rho$, and see what happens to the sign of the variance as $n \to \infty$. Apr 14, 2020 at 15:19
• In the limit I do see the problem, but In general that is not a problem. That is where I see the struggle Apr 14, 2020 at 15:53
• It's not in the limit. Regardless of what $\rho < 0$ you choose, there is a finite $n$ for which the variance is negative, and remains negative for all greater $n$. This means the proof fails. It's not a proof if it only works for certain combinations of $\rho$ and $n$ and fails for all the rest. Note also that for any given $\rho$, the number of $n$s for which the proof fails is countably infinitely greater than the (finite) number for which it works. Apr 14, 2020 at 16:03
• True that! Thanks Apr 14, 2020 at 16:04
• Feel free to add it as an answer Apr 14, 2020 at 16:05

The proof doesn't hold for $$\rho < 0$$, as for any $$\rho < 0$$, there exists an $$n_0$$ such that for all $$n \geq n_0$$, $$\rho + \frac{1-\rho}{n} < 0$$, and therefore the calculated variance $$V(\frac{1}{n} \sum X_i)$$ will be less than $$0$$ as well.
We can easily find $$n_0$$, as it is the smallest integer greater than or equal to $$-(1-\rho)/\rho$$.