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$?

  • $\begingroup$ 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$. $\endgroup$
    – jbowman
    Commented Apr 14, 2020 at 15:19
  • $\begingroup$ In the limit I do see the problem, but In general that is not a problem. That is where I see the struggle $\endgroup$
    – CutePoison
    Commented Apr 14, 2020 at 15:53
  • $\begingroup$ 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. $\endgroup$
    – jbowman
    Commented Apr 14, 2020 at 16:03
  • $\begingroup$ True that! Thanks $\endgroup$
    – CutePoison
    Commented Apr 14, 2020 at 16:04
  • $\begingroup$ Feel free to add it as an answer $\endgroup$
    – CutePoison
    Commented Apr 14, 2020 at 16:05

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.