Visual walkthrough — Bagging and bootstrap aggregating

We are going to answer one question: when you average many wobbly guesses, how much does the wobble shrink — and what stops it from shrinking to zero?

Step 0 — What is a "wobbly guess"? (setting the stage)

WHAT. Picture one machine — say a decision tree — that looks at a fresh input point $x$ and spits out a number, its prediction. Call that number ${\hat{f}}_1(x)$. The little hat "$\hat{}$" just means estimate — a guess, not the truth. The subscript $1$ means "machine number 1."

There is also a true answer we wish we knew, the real target value at $x$. We write it $f(x)$ — no hat, because it is the truth, not a guess. Keep both in mind: ${\hat{f}}_b(x)$ is a machine's attempt at the true $f(x)$.

WHY treat it as random? Because we trained it on a resampled copy of the data (a bootstrap sample). Shuffle the deck differently and the tree comes out slightly different, so its guess ${\hat{f}}_b(x)$ jumps around. A quantity that jumps around when you re-run the experiment is exactly what mathematicians call a random variable.

PICTURE. Below, one tree is asked the same question many times, each time trained on a differently-shuffled deck. Every white dot is one guess. They scatter around a centre.

$\mathbb{E}[{\hat{f}}_b(x)]=\mu \mathrm{Var}({\hat{f}}_b(x))={\sigma }^2$

Term by term:

• $\mathbb{E}[\cdot ]$ reads "expected value of" — imagine running the experiment a million times and taking the plain average. It returns the centre $\mu$.
• $\mathrm{Var}(\cdot )$ reads "variance of" — the average squared distance from that centre. It returns the spread ${\sigma }^2$.

Step 1 — The averaging move

WHAT. Instead of trusting one tree, we build $B$ of them (say $B=50$) on $B$ different decks, then average their guesses:

$\bar{f}(x)=\frac{1}{B}{\sum }_{b=1}^B{\hat{f}}_b(x).$

Reading the symbols left to right:

• $\bar{f}$ — the bar on top means "averaged." This is the whole ensemble's single answer.
• $\frac{1}{B}$ — divide by how many trees there are (that is what "average" means).
• ${\sum }_{b=1}^B$ — the $\sum$ ("sigma", capital S for Sum) says add up, letting the counter $b$ run from tree $1$ to tree $B$.

WHY average and not, say, pick the best? Because we don't know which tree is best on a new point — its errors are random. Averaging is the one operation that lets opposite errors cancel: a tree guessing too high pairs with one guessing too low.

PICTURE. Many clouds collapsing toward one tight centre.

Step 2 — Averaging does NOT move the aim (bias is untouched)

WHAT. We compute the centre of the averaged guess $\bar{f}$.

WHY this first? Before celebrating a tighter cloud, we must check we didn't drag the aim off-target. A tight cloud around the wrong spot is useless.

The tool we need is linearity of expectation: the average of sums is the sum of averages. $\mathbb{E}$ can slide through $+$ and through constant multipliers untouched. That is the only property we use here, and it is always true — no independence required.

$\mathbb{E}[\bar{f}(x)]=\mathbb{E}\left[\frac{1}{B}{\sum }_{b=1}^B{\hat{f}}_b(x)\right]=\frac{1}{B}{\sum }_{b=1}^B\underset{=\mu }{\underbrace{\mathbb{E}[{\hat{f}}_b(x)]}}=\frac{1}{B}\cdot B\mu =\mu .$

• Pull the constant $\frac{1}{B}$ out front (allowed — linearity).
• Each inner expectation is $\mu$ (all trees have the same aim).
• Add $\mu$ to itself $B$ times $\to B\mu$; the $B$ cancels the $\frac{1}{B}$.

Result: the aim is still $\mu$, so the bias $\mu -f(x)$ is exactly what it was for one tree. Same centre. This is why bagging cannot fix bias — it only reshapes the cloud, never relocates it.

PICTURE. The single tree's centre and the ensemble's centre sit at the exact same dashed line; only the width differs.

Step 3 — The variance of a sum: the honest bookkeeping

WHAT. Now the payoff — the spread of $\bar{f}$. To get there we need one general fact about the variance of a weighted sum. Let $X_1,\dots ,X_B$ be any random numbers and $a_1,\dots ,a_B$ fixed weights (in a moment we will set $X_i={\hat{f}}_i(x)$, the $i$-th tree's guess, and $a_i=\frac{1}{B}$ — the $X_i$ are our trees, nothing more exotic):

$\mathrm{Var}\left({\sum }_i{a}_i{X}_i\right)={\sum }_i{a}_i^2\mathrm{Var}(X_i)+{\sum }_{i\ne j}{a}_i{a}_j\mathrm{Cov}(X_i,X_j).$

WHY does the second sum appear at all? Variance is built from squares: $\mathrm{Var}(Y)=\mathbb{E}[(Y-\text{mean}{)}^2]$. When $Y={\sum }_i{a}_i{X}_i$, squaring a sum produces every cross-term $a_i{a}_j{X}_i{X}_j$, not just the squares $a_i^2{X}_i^2$ — think of $(p+q{)}^2=p^2+q^2+2pq$: the $2pq$ is the cross-term. Each cross-term measures how tree $i$ and tree $j$ move together, which is exactly the covariance. So "add the variances alone" ($\sum a_i^2\mathrm{Var}(X_i)$) is only correct when every cross-term vanishes — i.e. when the $X_i$ are independent. Our trees share the original dataset, so they err together and the cross-terms survive.

PICTURE. Squaring a sum of two arrows fills a $2\times 2$ block — two diagonal "square" tiles and two off-diagonal "cross" tiles. Those cross tiles are the covariances.

Step 4 — Plug in our specific numbers

WHAT. Set $X_i={\hat{f}}_i(x)$ and the weights $a_i=\frac{1}{B}$. Every tree has variance ${\sigma }^2$; every distinct pair has covariance $\rho {\sigma }^2$. Now count the cells in the full pair-grid:

• Diagonal cells (tree with itself): there are $B$ of them, each contributing ${\left(\frac{1}{B}\right)}^2{\sigma }^2$.
• Off-diagonal cells (distinct pairs): a $B\times B$ grid has $B^2$ cells; remove the $B$ diagonal ones, leaving $B(B-1)$ pairs, each contributing ${\left(\frac{1}{B}\right)}^2\rho {\sigma }^2$.

$\mathrm{Var}(\bar{f})=\frac{1}{B^2}[\underset{\text{the }B\text{ diagonals}}{\underbrace{B{\sigma }^2}}+\underset{\text{the }B(B-1)\text{ pairs}}{\underbrace{B(B-1)\rho {\sigma }^2}}].$

WHY count so carefully? Because the whole punchline lives in the ratio of these two counts. As $B$ grows, the off-diagonal cells ($\approx B^2$ of them) vastly outnumber the diagonal ones ($B$ of them) — so the shared-error term will refuse to die. That is the floor, forming before our eyes.

PICTURE. The full grid, now shaded: a thin diagonal ribbon (shrinking share) versus a huge off-diagonal field (dominant share).

Step 5 — Simplify to the boxed law

WHAT. Expand the bracket and divide each piece by $B^2$:

$\mathrm{Var}(\bar{f})=\frac{B{\sigma }^2}{B^2}+\frac{B(B-1)\rho {\sigma }^2}{B^2}=\frac{{\sigma }^2}{B}+\frac{(B-1)}{B}\rho {\sigma }^2.$

Rewrite $\frac{B-1}{B}=1-\frac{1}{B}$ and regroup so the $\rho {\sigma }^2$ terms sit together:

$\frac{{\sigma }^2}{B}+\rho {\sigma }^2-\frac{\rho {\sigma }^2}{B}=\rho {\sigma }^2+\frac{{\sigma }^2-\rho {\sigma }^2}{B}.$

WHY regroup this way? We want to physically separate the two behaviours the reader cares about: the part that survives forever (no $B$ attached) from the part that melts as $B$ grows (carries a $\frac{1}{B}$). Collecting all the $\rho {\sigma }^2$ without a $\frac{1}{B}$ into one bucket, and everything with a $\frac{1}{B}$ into another, makes those two fates literally sit side by side.

$\boxed{\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2}$

Term by term — read this like a dashboard:

• $\rho {\sigma }^2$ — the floor. It has no $B$ in it. Adding trees can never touch it. It is set purely by how alike the trees are.
• $\frac{1-\rho }{B}{\sigma }^2$ — the meltable part. It carries a $\frac{1}{B}$, so it shrinks toward $0$ as you add trees.

Step 6 — Cover every case (the edges)

A law you can't stress-test isn't understood. Push the two knobs $\rho$ and $B$ to their extremes.

Case A — $\rho =0$ (independent trees). Floor $=0$. Variance $=\frac{{\sigma }^2}{B}$: the classic "divide by $B$." Ten trees → one-tenth the wobble. This is the dream, rarely reachable because trees share data.

Case B — $\rho =1$ (clone trees, e.g. a stable learner like linear regression). Floor $={\sigma }^2$; meltable part $=\frac{1-1}{B}{\sigma }^2=0$. Variance stays ${\sigma }^2$ no matter how many trees — bagging does nothing. This is the parent note's "don't bag stable models" mistake, proven.

Case C — $B=1$ (one tree). $\mathrm{Var}=\rho {\sigma }^2+(1-\rho ){\sigma }^2={\sigma }^2$. Sanity check: one tree must have its own variance ${\sigma }^2$. ✓

Case D — $B\to \infty$ (infinite trees). The $\frac{1}{B}$ term vanishes; $\mathrm{Var}\to \rho {\sigma }^2$. You hit the floor. The only escape left is to lower $\rho$ — which is exactly why Random Forests inject extra randomness at each split.

PICTURE. Variance-versus-$B$ curves for several $\rho$ values, each flattening onto its own floor $\rho {\sigma }^2$.

The one-picture summary

Everything above lives in one diagram: the total variance is a floor you cannot melt plus a puddle that adding trees melts away.

Recall