Bagging and bootstrap aggregating: Worked examples

This is the worked-example lab for Bagging and bootstrap aggregating. The parent note built the two engines: the variance formula and the out-of-bag fraction $(1 - \frac{1}{n})^{n} \to e^{- 1}$ . Here we push both to every corner: every value of $ρ$ (negative, zero, positive, the ceiling $ρ = 1$ ), every size of $B$ (one model, ten, infinity), classification votes (odd and even $B$ ), small- $n$ vs. large- $n$ bootstrap, and a couple of exam traps.

Before we start, three quantities and one new symbol we will lean on constantly:

Definition The symbols in play (including

$\overset{ˉ}{f}$ )

$\hat{f}_{b} (x)$ = the prediction of one base tree number $b$ at input $x$ .
$\overset{ˉ}{f} (x)$ = the ensemble average predictor — literally the average of all $B$ trees' outputs, $\overset{ˉ}{f} (x) = \frac{1}{B} \sum_{b = 1}^{B} \hat{f}_{b} (x)$ . The bar on top means "average of." This is the single number the bagged model finally reports. Whenever you see $\overset{ˉ}{f}$ below, read it as "the whole forest's averaged answer."
$σ^{2}$ = the variance of a single base model — how much one tree's prediction wobbles if you reshuffle its training data. Think "how jumpy is one guesser."
$ρ$ = the pairwise correlation between two trees, a number from $- 1$ to $1$ . $ρ < 0$ means the trees make opposite mistakes (one too high when the other is too low); $ρ = 0$ means unrelated mistakes; $ρ = 1$ means the exact same mistake every time.
$B$ = how many trees we average.

With those named, the parent's boxed result reads: $Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2} .$ If any of these feel shaky, the parent's "WHY does averaging help?" section builds them from zero.

The scenario matrix

Every question bagging can ask you falls into one of these cells. The examples below are labelled by cell.

#	Cell (the case class)	What makes it special	Example
A	$ρ = 0$ (independent)	floor term vanishes, pure $1/ B$ drop	Ex 1
B	$0 < ρ < 1$ (correlated, realistic)	floor $ρ σ^{2}$ dominates	Ex 2
C	$ρ = 1$ (degenerate: identical models)	zero variance reduction	Ex 3
D	$B \to \infty$ (limiting behaviour)	variance hits its floor exactly	Ex 4
E	$ρ < 0$ (anti-correlated)	floor drops below $0$ -case, best of all	Ex 4b
F	Classification, odd $B$ majority vote	binomial, clean majority	Ex 5
G	Vote with correlated errors	the "jump" collapses	Ex 6, 6c
H	Classification, even $B$ (ties!)	tie-breaking rule needed	Ex 6b
I	Bootstrap, small $n$ (exact)	$e^{- 1}$ is a limit, not the truth for tiny $n$	Ex 7
J	Real-world word problem	translate English → the formula	Ex 8
K	Exam twist: "how many trees do I need?"	solve the formula for $B$	Ex 9

Two figures carry the derivation. Figure s01 plots ensemble variance $Var (\overset{ˉ}{f})$ (vertical axis) against the number of trees $B$ (horizontal axis) with one curve per $ρ$ : green $ρ = - 0.1$ dips lowest, yellow $ρ = 0$ falls as $1/ B$ , blue $ρ = 0.5$ flattens onto its dashed floor at $2$ , pink $ρ = 1$ is a flat line at $4$ . Figure s02 plots ensemble accuracy (vertical) against single-voter accuracy $p$ (horizontal): the yellow "5 voters" curve arches above the dashed diagonal (single voter), the green "4 voters, ties lose" curve can dip below the diagonal, and three dots mark Ex 5, Ex 6, Ex 6b. Read each cell straight off the picture.

Figure — Bagging and bootstrap aggregating

Cells A–E: the variance formula, corner by corner

Worked example Ex 1 — Cell A: independent models,

$ρ = 0$ One tree has $σ^{2} = 4$ . Bag $B = 10$ independent trees. Find $Var (\overset{ˉ}{f})$ .

Forecast: guess before reading — will the variance drop by exactly $10 \times$ , more, or less?

Write the formula: $Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ . Why this step? It is the only tool that connects $ρ, σ^{2}, B$ to the ensemble's wobble.
Plug $ρ = 0$ : the first term $ρ σ^{2} = 0 \cdot 4 = 0$ disappears. Why this step? With no correlation there is no floor — nothing stops the averaging.
Second term: $\frac{1 - 0}{10} \cdot 4 = \frac{4}{10} = 0.4$ . Why this step? Independent noise averages down cleanly as $σ^{2} / B$ .

Answer: $Var (\overset{ˉ}{f}) = 0.4$ . A clean $10 \times$ cut, matching the forecast if you guessed "exactly $10 \times$ ."

Verify: $σ^{2} / B = 4/10 = 0.4$ . ✓ Units: variance stays in (prediction-units)², consistent. On figure s01 this is the yellow curve, passing through $0.4$ at $B = 10$ .

Worked example Ex 4 — Cell D (limit):

$B \to \infty$ Take the $ρ = 0.5, σ^{2} = 4$ setup and let $B$ grow without bound. What is the best variance we can ever reach with plain bagging?

Forecast: does it go to $0$ , or stall somewhere?

In $Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ , send $B \to \infty$ . Why this step? We want the ceiling on our reward — the reason more trees eventually stop helping.
The second term $\frac{1 - ρ}{B} σ^{2} \to 0$ because a fixed number divided by an exploding $B$ collapses. Why this step? This term is the "averaging away noise" part; infinite averaging finishes it.
What remains: $ρ σ^{2} = 0.5 \cdot 4 = 2$ .

Answer: the variance floor is $2$ . Look at the blue curve in figure s01 (labelled in the legend): it drops fast then flattens onto the dashed floor line at $2$ . To go lower you must lower $ρ$ (that is literally why Random Forests exist — see Bias-Variance Tradeoff).

Verify: substitute the numbers first, then take the limit. With $ρ = 0.5, σ^{2} = 4$ the averaging term is $\frac{1 - 0.5}{B} \cdot 4 = \frac{2}{B}$ , so $Var = 2 + \frac{2}{B}$ . At $B = 1000$ : $2 + 2/1000 = 2.002 \approx 2$ ; as $B \to \infty$ the $\frac{2}{B} \to 0$ , leaving exactly $2$ . ✓

Worked example Ex 4b — Cell E (negative correlation):

$ρ = - 0.2$ then a legal value Suppose you could engineer trees whose errors oppose each other, giving $ρ = - 0.2$ . Same $σ^{2} = 4$ , $B = 10$ . Find $Var (\overset{ˉ}{f})$ , and the $B \to \infty$ floor.

Forecast: the formula allows $ρ$ down to $- 1$ in spirit. Does negative $ρ$ beat the independent case ( $0.4$ ), or is $0.4$ already the best possible?

Floor term with $ρ = - 0.2$ : $ρ σ^{2} = (- 0.2) \cdot 4 = - 0.8$ . Why this step? When errors anti-correlate, one tree's over-shoot is cancelled by another's under-shoot, so the shared part is now a credit, not a cost.
Averaging term: $\frac{1 - ( - 0.2 )}{10} \cdot 4 = \frac{1.2}{10} \cdot 4 = 0.48$ . Why this step? The "still-averageable" slice is $1 - ρ = 1.2$ , larger than $1$ , because negative correlation adds extra cancellable noise on top of the independent amount.
Add: $- 0.8 + 0.48 = - 0.32$ — stop, a variance cannot be negative! Why this step? A negative result is a red flag that our inputs were illegal, not that the formula is wrong. Check the feasibility bound from the definition box: for $B = 10$ , $ρ \geq - \frac{1}{B - 1} = - \frac{1}{9} \approx - 0.111$ . Since $- 0.2 < - 0.111$ , $ρ = - 0.2$ is not achievable by 10 equally-correlated trees.
Use a legal negative value just inside the bound, $ρ = - 0.1$ : floor $= - 0.1 \cdot 4 = - 0.4$ ; averaging $= \frac{1 - ( - 0.1 )}{10} \cdot 4 = \frac{1.1}{10} \cdot 4 = 0.44$ ; total $= - 0.4 + 0.44 = 0.04$ . Why this step? Now the answer is a legal, positive variance — and it is below the independent $0.4$ , proving anti-correlation is the best regime.

Answer: with the feasible $ρ = - 0.1$ , $Var (\overset{ˉ}{f}) = 0.04$ , better than the independent $0.4$ . As $B$ grows the feasibility bound $- \frac{1}{B - 1} \to 0^{-}$ squeezes the achievable negativity toward $0$ , so this bonus fades for large forests.

Verify: $- 0.1 \cdot 4 + (1.1/10) \cdot 4 = - 0.4 + 0.44 = 0.04$ ✓, and $0.04 < 0.4$ ✓. Feasibility: $- 1/ (B - 1) = - 1/9 \approx - 0.111 \leq - 0.1$ ✓. On figure s01 the green curve sits below the yellow one — negative $ρ$ wins.

Cells F–H: classification by voting

Averaging numbers (regression) and taking a majority vote (classification) behave differently, so voting gets its own tool.

Worked example Ex 5 — Cell F: independent majority vote, odd

$B$ $5$ independent classifiers, each correct with $p = 0.7$ . The ensemble is correct if $\geq 3$ agree. Find ensemble accuracy.

Forecast: more than $0.7$ , less, or the same?

Need $k = 3, 4, 5$ correct out of $5$ : $P = \sum_{k = 3}^{5} (k 5) 0. 7^{k} 0. 3^{5 - k}$ . Why this step? "Majority of 5" = at least 3 (since $\frac{5 + 1}{2} = 3$ ); we add up every winning count.
$k = 3$ : $(3 5) = 10$ , $10 \cdot 0. 7^{3} \cdot 0. 3^{2} = 10 \cdot 0.343 \cdot 0.09 = 0.3087$ . Why this step? This is the probability of the tightest win — exactly 3 right, 2 wrong; there are $(3 5) = 10$ ways to choose which 3 are right.
$k = 4$ : $(4 5) = 5$ , $5 \cdot 0. 7^{4} \cdot 0. 3^{1} = 5 \cdot 0.2401 \cdot 0.3 = 0.36015$ . Why this step? Probability of exactly 4 right, 1 wrong, over $(4 5) = 5$ arrangements — a more comfortable win.
$k = 5$ : $(5 5) = 1$ , $1 \cdot 0. 7^{5} = 0.16807$ . Why this step? The unanimous case — all 5 right, only $(5 5) = 1$ way. Summing these three disjoint events gives "at least 3 right."
Add: $0.3087 + 0.36015 + 0.16807 = 0.83692$ . Why this step? The three counts are mutually exclusive, so total probability is their sum.

Answer: $\approx 0.837$ . Accuracy jumped $0.70 \to 0.84$ — the yellow point on figure s02, sitting above the diagonal "single classifier" line (see legend).

Verify: $0.3087 + 0.36015 + 0.16807 = 0.83692$ . ✓ Sanity: $0.837 > 0.7$ , majority of good voters is better than one.

Worked example Ex 6 — Cell G: perfectly correlated errors (

$ρ = 1$ ) Push it to the degenerate extreme: all $5$ classifiers are perfectly correlated (they always agree — effectively one classifier). Each still individually correct with $p = 0.7$ .

Forecast: does the vote still land near $0.84$ ?

If all $5$ always agree, the "majority" is just what any one of them says. Why this step? Perfect correlation ( $ρ = 1$ ) means there is really only one independent opinion, cloned 5 times.
So ensemble accuracy $= p = 0.7$ . Why this step? No error can cancel — the votes cannot disagree, so nothing averages.

Answer: $0.70$ — the entire gain of Ex 5 vanished. This is the classification twin of Cell C. The pink point on figure s02 sits back on the diagonal.

Verify: correlated-limit accuracy $= p = 0.70$ . Gap lost $= 0.837 - 0.70 = 0.137$ . ✓ Diversity was the whole point.

Worked example Ex 6c — Cell G (partial correlation

$0 < ρ < 1$ ): a mixture model Reality is between Ex 5 and Ex 6. Model $5$ voters as follows: with probability $λ = 0.5$ they all copy one shared coin (fully correlated), and with probability $1 - λ = 0.5$ they vote independently. Each individual voter is correct with $p = 0.7$ . Find ensemble accuracy. (This mixture is the simplest way to dial a partial error-correlation between the two extremes.)

Forecast: somewhere between $0.70$ (Ex 6) and $0.837$ (Ex 5) — but closer to which end?

Split by the mixture: $P = λ \cdot P_{correlated} + (1 - λ) \cdot P_{independent}$ . Why this step? The two "modes" (all-copy vs. independent) are mutually exclusive scenarios, so we weight each by how often it happens and add — the law of total probability.
Correlated mode accuracy $= p = 0.7$ (from Ex 6). Why this step? When all copy one coin, the majority equals that one voter's correctness.
Independent mode accuracy $= 0.83692$ (from Ex 5). Why this step? When independent, we reuse the binomial majority we already computed.
Combine: $P = 0.5 \cdot 0.7 + 0.5 \cdot 0.83692 = 0.35 + 0.41846 = 0.76846$ . Why this step? Plug the two mode-accuracies into step 1.

Answer: $\approx 0.768$ — squarely between the two extremes. Partial correlation gives you part of the boost: half the diversity buys roughly half the gain over $0.70$ .

Verify: $0.5 \cdot 0.7 + 0.5 \cdot 0.83692 = 0.76846$ , and $0.70 < 0.76846 < 0.83692$ ✓. Sanity: at $λ = 0$ (never correlated) it returns $0.837$ ; at $λ = 1$ (always correlated) it returns $0.70$ ✓.

Worked example Ex 6b — Cell H: even

$B$ and the tie problem Now $B = 4$ independent classifiers, each correct with $p = 0.7$ . A $2$ – $2$ split is a tie. Compute the accuracy under two tie rules: (i) tie counts as wrong, (ii) tie broken by fair coin.

Forecast: will $4$ voters beat, tie, or trail the $5$ -voter $0.837$ ?

Clean wins need $k \geq 3$ (strict majority of 4): $P_{win} = (3 4) 0. 7^{3} 0. 3^{1} + (4 4) 0. 7^{4}$ . Why this step? With $B = 4$ , a strict majority is $3$ or $4$ correct; $2$ – $2$ is not a win. The $0. 3^{1}$ is written with its explicit exponent $1$ so no power stays hidden.
Compute: $(3 4) = 4$ , $4 \cdot 0. 7^{3} \cdot 0. 3^{1} = 4 \cdot 0.343 \cdot 0.3 = 0.4116$ ; $(4 4) = 1$ , $0. 7^{4} = 0.2401$ . So $P_{win} = 0.4116 + 0.2401 = 0.6517$ . Why this step? These are the unambiguous majorities, computed before any tie handling.
Tie probability ( $k = 2$ ): $(2 4) 0. 7^{2} 0. 3^{2} = 6 \cdot 0.49 \cdot 0.09 = 0.2646$ . Why this step? The $2$ – $2$ mass must be handled separately because its outcome depends on which tie rule we adopt — it is neither automatically a win nor a loss.
Rule (i) tie = wrong: accuracy $= P_{win} = 0.6517$ . Why this step? Under this rule the entire tie mass counts as failures, so only strict wins survive.
Rule (ii) fair coin: accuracy $= P_{win} + \frac{1}{2} (tie) = 0.6517 + \frac{1}{2} (0.2646) = 0.6517 + 0.1323 = 0.7840$ . Why this step? A fair coin recovers exactly half the tie mass as correct answers.

Answer: with ties-lose, $4$ voters give $0.6517$ — worse than a single voter's $0.7$ ! With coin-flip ties, $0.784$ — better than one voter but still below the $5$ -voter $0.837$ . Lesson: even $B$ wastes voters on ties; use odd $B$ .

Verify: $P_{win} = 0.6517$ ; tie $= 0.2646$ ; coin-flip $= 0.784$ . Full probability check: $P (k \leq 1) = (0 4) 0. 3^{4} + (1 4) 0.7 \cdot 0. 3^{3} = 0.0081 + 0.0756 = 0.0837$ , and $0.6517 + 0.2646 + 0.0837 = 1.0$ ✓.

Cell I: the bootstrap for small $n$ (exact, not the limit)

Worked example Ex 7 — Cell I: exact OOB fraction for

$n = 5$ A dataset has only $n = 5$ points. What fraction of the data is out-of-bag for one bootstrap sample?

Forecast: exactly $37%$ , more, or less?

Probability one specific point is missed in a single draw: $1 - \frac{1}{n} = 1 - \frac{1}{5} = 0.8$ . Why this step? Each draw picks one of $5$ points uniformly; "not this point" has probability $4/5$ .
It must be missed on all $5$ independent draws: $(0.8)^{5}$ . Why this step? With replacement, draws are independent, so multiply.
$(0.8)^{5} = 0.32768$ . Why this step? Raising the single-draw miss probability to the power $n = 5$ gives the all-draws miss.

Answer: $\approx 0.3277$ , i.e. about $32.8%$ — noticeably below the asymptotic $36.8%$ .

Verify: $(1 - 1/5)^{5} = 0.32768$ . Compare $e^{- 1} = 0.3679$ ; difference $\approx 0.040$ . ✓ Small $n$ ⇒ less gets left out. (The Bootstrap machinery: Bootstrap (statistics); the free-validation trick: Out-of-Bag Error.)

Cell J: a real-world word problem

Worked example Ex 8 — Cell J: how much wobble is left after bagging a forest?

A single deep decision tree (Decision Trees) predicts house prices measured in thousands of dollars, so its prediction variance is $σ^{2} = 900$ (thousands of dollars)² — i.e. a standard deviation of $900 = 30$ thousand dollars. You bag $B = 50$ trees. Because they share training data, their pairwise correlation is $ρ = 0.2$ . What is the bagged variance $Var (\overset{ˉ}{f})$ , and how much came from the floor vs. the averaging?

Forecast: guess whether the floor or the $1/ B$ term dominates.

Floor term: $ρ σ^{2} = 0.2 \cdot 900 = 180$ . Why this step? This is the irreducible part — 50 trees or 5 million, it stays $180$ .
Averaging term: $\frac{1 - ρ}{B} σ^{2} = \frac{0.8}{50} \cdot 900 = \frac{0.8 \cdot 900}{50} = \frac{720}{50} = 14.4$ . Why this step? The $80%$ un-correlated slice averages down by $50$ .
Total: $180 + 14.4 = 194.4$ . Why this step? Add floor and averaging parts, as the formula prescribes.

Answer: $Var (\overset{ˉ}{f}) = 194.4$ (thousands of dollars)², down from $900$ — a $\sim 4.6 \times$ reduction (standard deviation drops from $30$ to $194.4 \approx 13.9$ thousand dollars). The floor ( $180$ ) is $\approx 93%$ of what remains, so more trees would barely help; lowering $ρ$ (feature subsampling → Random Forests) is the lever.

Verify: $0.2 \cdot 900 + (0.8/50) \cdot 900 = 180 + 14.4 = 194.4$ . Fraction from floor: $180/194.4 \approx 0.926$ . ✓ Units: every term is (thousands of dollars)², consistent throughout.

Cell K: the exam twist — solve for $B$

Worked example Ex 9 — Cell K: how many trees to hit a target variance?

With $σ^{2} = 4$ and $ρ = 0.3$ , you want $Var (\overset{ˉ}{f}) \leq 1.3$ . What is the smallest integer $B$ that works?

Forecast: single digits? Tens? Is $1.3$ even reachable?

First check the floor: $ρ σ^{2} = 0.3 \cdot 4 = 1.2$ . Since $1.2 < 1.3$ , the target is reachable (a target below $1.2$ would be impossible at any $B$ ). Why this step? No point solving for $B$ if the goal sits under the floor.
Set up the inequality: $1.2 + \frac{1 - 0.3}{B} \cdot 4 \leq 1.3$ , i.e. $\frac{0.7 \cdot 4}{B} \leq 0.1$ . Why this step? Everything above the floor must fit inside the $0.1$ budget we have left.
Simplify: $\frac{2.8}{B} \leq 0.1 \Rightarrow B \geq \frac{2.8}{0.1} = 28$ . Why this step? Isolate $B$ — dividing flips nothing since all quantities are positive.
Smallest integer: $B = 28$ . Why this step? $B$ must be a whole number of trees, and $28$ is the first that satisfies $B \geq 28$ .

Answer: $B = 28$ trees.

Verify: at $B = 28$ : $1.2 + (2.8/28) = 1.2 + 0.1 = 1.3 \leq 1.3$ ✓. At $B = 27$ : $1.2 + 2.8/27 = 1.2 + 0.1037 = 1.3037 > 1.3$ ✗. So $28$ is minimal. ✓

Recall Quick self-test across the matrix

Ex 1 gave which variance ( $ρ = 0$ , $σ^{2} = 4$ , $B = 10$ )? ::: $0.4$ Ex 2 ( $ρ = 0.5$ ) gave? ::: $2.2$ With $ρ = 1$ , bagging changes variance by how much? ::: Nothing — stays $σ^{2}$ . The $B \to \infty$ floor for $ρ = 0.5, σ^{2} = 4$ ? ::: $2$ With feasible $ρ = - 0.1$ ( $σ^{2} = 4, B = 10$ ), variance is? ::: $0.04$ — better than the independent $0.4$ . Why can't $ρ$ be as negative as you like for $B$ trees? ::: Feasibility bound $ρ \geq - \frac{1}{B - 1}$ . Ensemble accuracy of 5 independent $p = 0.7$ voters? ::: $\approx 0.837$ Same 5 voters but perfectly correlated? ::: $0.70$ (gain lost) Ex 6c mixture ( $λ = 0.5$ ) accuracy? ::: $\approx 0.768$ — halfway between the extremes. 4 independent $p = 0.7$ voters, ties-lose? ::: $0.6517$ — worse than one voter! Why prefer odd $B$ in majority vote? ::: No ties; a strict majority always exists. Exact OOB fraction for $n = 5$ ? ::: $(0.8)^{5} = 0.32768$ , below $37%$ . Fewest trees for Var $\leq 1.3$ with $ρ = 0.3, σ^{2} = 4$ ? ::: $28$

Related roads onward: Ensemble Methods frames all of this; Boosting is the other branch (it reduces bias, unlike bagging). Hinglish version: 2.3.06 Bagging and bootstrap aggregating (Hinglish).