Visual walkthrough — Random forest algorithm

Read this if the algebra in the parent felt like magic. By the end you will see the floor.

Prerequisites we lean on: Bagging (Bootstrap Aggregating) (the row-sampling that makes many trees), Decision Trees (the wobbly expert we are averaging), and Bias-Variance Tradeoff (why "wobble" is a thing worth killing).

---

Step 1 — What is "variance", drawn as a spread of darts?

WHAT. Before any formula, pin down the one word everything rests on. A prediction from a tree is not a fixed number — retrain the same tree on a slightly different sample and it gives a slightly different answer. So a prediction is a random variable: a number that jitters around some centre.

Variance is just how wide that jitter is. Write it $\mathrm{Var}(f)$ for a tree's prediction $f$. If we call the average value $\mu$ (the centre of the cloud), then

$\mathrm{Var}(f)=\underset{\text{over many retrains}}{\underbrace{\text{average of}}}(\underset{\text{a jittery answer}}{\underbrace{f}}-\underset{\text{its centre}}{\underbrace{\mu }}{)}^2.$

The square makes every miss positive (left and right misses both count) and punishes big misses more. We name this width ${\sigma }^2$, so $\mathrm{Var}(f)={\sigma }^2$. The plain letter $\sigma$ (its square root) is the typical distance from centre.

WHY this tool. We want to measure "how unreliable is one tree?" Not its bias (is the centre right?) but its shakiness. Variance is exactly the shakiness meter.

PICTURE. Think darts on a board: the centre is $\mu$, the scatter of the darts is $\sigma$.

---

Step 2 — Averaging many independent darts shrinks the spread

WHAT. Now take $B$ trees, predictions $f_1,\dots ,f_B$, and average them: $\bar{f}=\frac{1}{B}{\sum }_{b=1}^B{f}_b$. Here $B$ is simply how many trees and $\bar{f}$ (f-with-a-bar) is their mean vote. Suppose for now the trees are independent — their jitters have nothing to do with each other, like darts thrown by strangers in separate rooms.

WHY averaging. When one tree overshoots and another undershoots, the two errors partly cancel. Independence means the cancellations are as good as it gets. The question we are answering: how much steadier is the crowd's answer than one member's?

The rule for independent variables: variance of an average is

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

Each symbol: ${\sigma }^2$ is one tree's spread, $B$ is the crowd size, and dividing by $B$ says the crowd's spread is $B$ times narrower. Ten independent trees → one-tenth the variance. A hundred → one-hundredth.

PICTURE. The single-tree dart cloud is fat; the average-of-many cloud is a tight knot around the same centre.

---

Step 3 — Correlation: when the darts move together

WHAT. Two trees are correlated when their jitters are linked: if tree $i$ overshoots, tree $j$ tends to overshoot too. We measure the link between a pair with the covariance $\mathrm{Cov}(f_i,f_j)$ — the average of (how far $i$ is from its centre) $\times$ (how far $j$ is from its centre). Same-direction misses ⇒ positive; opposite ⇒ negative; unrelated ⇒ zero.

To get a unitless number between $-1$ and $1$ we divide covariance by the spreads, giving the correlation $\rho$ (Greek "rho"):

$\rho =\frac{\mathrm{Cov}(f_i,f_j)}{{\sigma }^2}⟹\mathrm{Cov}(f_i,f_j)=\rho {\sigma }^2.$

Reading it: $\rho {\sigma }^2$ is the shared wobble between any two trees. $\rho =0$ ⇒ strangers (Step 2's happy case). $\rho =1$ ⇒ clones (they never disagree). Forests live in between.

WHY this tool. Averaging only cancels errors that disagree. Correlation is precisely the meter for "how much do the trees agree by default" — so it must control how well averaging works. We introduce $\rho$ now because the next step needs exactly this quantity.

PICTURE. Two dart clouds for a pair of trees: strangers scatter in a round blob ($\rho \approx 0$); clones line up on a diagonal ($\rho \approx 1$).

---

Step 4 — The variance of a sum: count the boxes

WHAT. To average, first sum. So compute $\mathrm{Var}\left({\sum }_b{f}_b\right)$. The exact rule (the definition of variance applied to a sum) is: add up every tree's own variance, then add every cross-term covariance:

$\mathrm{Var}\left({\sum }_b{f}_b\right)=\underset{\text{diagonal}}{\underbrace{\sum _b\mathrm{Var}(f_b)}}+\underset{\text{off-diagonal}}{\underbrace{\sum _{i\ne j}\mathrm{Cov}(f_i,f_j)}}.$

WHY a grid. The cleanest way to see "every pair" is a $B\times B$ table where cell $(i,j)$ holds $\mathrm{Cov}(f_i,f_j)$. The diagonal cells are $\mathrm{Cov}(f_b,f_b)=\mathrm{Var}(f_b)={\sigma }^2$ — a tree with itself. The off-diagonal cells are $\rho {\sigma }^2$ from Step 3.

Count them.

• Diagonal cells: there are $B$ of them, each ${\sigma }^2$ → total $B{\sigma }^2$.
• Off-diagonal cells: a $B\times B$ grid has $B^2$ cells, minus $B$ on the diagonal = $B(B-1)$ cells, each $\rho {\sigma }^2$ → total $B(B-1)\rho {\sigma }^2$.

$\mathrm{Var}\left({\sum }_b{f}_b\right)=\underset{\text{diagonal boxes}}{\underbrace{B{\sigma }^2}}+\underset{\text{off-diagonal boxes}}{\underbrace{B(B-1)\rho {\sigma }^2}}.$

PICTURE. The grid, diagonal shaded one colour (${\sigma }^2$), off-diagonal another ($\rho {\sigma }^2$) — the whole formula is just counting coloured boxes.

---

Step 5 — Divide by $B^2$ to get the average, and read the two terms

WHAT. We wanted $\bar{f}=\frac{1}{B}\sum f_b$, not the sum. Scaling a random variable by a constant $a$ scales its variance by $a^2$; here $a=\frac{1}{B}$, so we divide the whole Step-4 result by $B^2$:

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

Split the fraction term-by-term:

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

Now rewrite $\frac{B-1}{B}=1-\frac{1}{B}$ and gather:

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

Term-by-term meaning:

• $\rho {\sigma }^2$ — the floor. It has no $B$ in it. Adding trees cannot touch it. It is the shared wobble that survives all averaging.
• $\frac{1-\rho }{B}{\sigma }^2$ — the meltable part. Growing $B$ shrinks it toward $0$. Notice when $\rho =0$ this whole formula collapses to Step 2's ${\sigma }^2/B$ — our independent case falls right out, a good sanity check.

PICTURE. A curve of $\mathrm{Var}(\bar{f})$ against the number of trees $B$: it drops fast, then flattens onto a horizontal line at height $\rho {\sigma }^2$.

---

Step 6 — Edge and degenerate cases (never leave the reader guessing)

WHAT. Push the formula to its extremes and read what each says.

PICTURE. Four floor-lines on the same axes, one per case.

• $\rho =0$ (independent trees). Formula → ${\sigma }^2/B$. Floor is $0$: infinitely many strangers do reach perfect steadiness. This is the ideal we can only approach.
• $\rho =1$ (clone trees, e.g. no feature randomness on data with one dominant feature). $\frac{1-\rho }{B}=0$ for all $B$, so $\mathrm{Var}(\bar{f})={\sigma }^2$. Averaging clones gives you one clone — no benefit at all. This is the disaster plain Bagging (Bootstrap Aggregating) risks and why the random feature-subset exists.
• $B=1$ (a single tree). $\rho {\sigma }^2+\frac{1-\rho }{1}{\sigma }^2={\sigma }^2$. Reassuring: "one tree's variance is one tree's variance." The formula is self-consistent at the boundary.
• $B\to \infty$. Second term $\to 0$; variance $\to \rho {\sigma }^2$. The floor, exactly. This is why the parent says "the real magic is lowering $\rho$, not raising $B$."

---

The one-picture summary

Everything on this page in one frame: a fat single-tree cloud → a $B\times B$ covariance grid (diagonal ${\sigma }^2$, off-diagonal $\rho {\sigma }^2$) → the decay curve landing on the floor $\rho {\sigma }^2$.

Recall Feynman retelling — the whole walkthrough in plain words

One decision tree is like a nervous friend whose answer wobbles depending on which examples she happened to study (Step 1 — that wobble is variance ${\sigma }^2$). Ask a hundred unrelated friends and average their answers, and the wobbles cancel — the crowd is a hundred times steadier (Step 2 — ${\sigma }^2/B$). But friends who all studied the same book give the same wobble; how alike they are is correlation $\rho$ (Step 3). To find the crowd's wobble exactly, lay every pair in a grid: the diagonal boxes are each friend's own wobble, the off-diagonal boxes are shared wobble, and you just count and add them (Step 4). Divide by the crowd size squared to turn the sum into an average, and the answer splits cleanly into two pieces: a floor $\rho {\sigma }^2$ that no amount of friends can remove, plus a meltable piece $\frac{1-\rho }{B}{\sigma }^2$ that shrinks as the crowd grows (Step 5). So if the friends are strangers ($\rho =0$) the floor is zero — but if they're clones ($\rho =1$) the crowd is no better than one person (Step 6). That is why a random forest doesn't just add trees; it forces each tree to look at different features, pushing $\rho$ down and lowering the floor itself.

---

Connections

• Parent: Random forest algorithm — the full algorithm this derivation powers.
• Bagging (Bootstrap Aggregating) — the $\rho =1$ danger this page warns about.
• Decision Trees — the wobbly base learner (${\sigma }^2$).
• Bias-Variance Tradeoff — why lowering $\rho$ can't come free (it raises ${\sigma }^2$).
• 2.3.07 Random forest algorithm (Hinglish) — same walkthrough in Hinglish.