The bagging variance formula

ProofIntermediate⏱ 30 minClassical MLbaggingvariancecorrelationrandom forest

Problem

Derive $\Var(\bar f) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2$ for the average of $B$ predictors with common variance $\sigma^2$ and pairwise correlation $\rho$ . Compute the limit, and explain precisely what random forests do about it and at what cost.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
The Δ²/12 noise variance	Quantization	Proof	Beginner	15 min
Concave impurity gives non-negative information gain	Classical ML	Proof	Intermediate	30 min
Gradient boosting fits the negative functional gradient	Classical ML	Proof	Intermediate	30 min
Mini-batching and the compute budget	SGD	Numerical	Intermediate	30 min
The 1/n variance rate requires uncorrelated samples	Probability	Numerical	Intermediate	30 min