Worked examples — Out-of-bag error estimation

A drill-book for Out-of-bag error estimation. We march through every case the OOB idea can throw at you: normal forests, tiny forests, degenerate points that are OOB for nobody, ties, regression vs classification, the large-$n$ limit, and a real-world twist. Guess before you read the steps.

Before anything, one plain-word refresher so no symbol arrives unearned:

---

The scenario matrix

Every OOB question is really one of these cells. The examples below are tagged with the cell they hit.

Cell	Case class	What makes it tricky	Example
A	Identify OOB set from one bootstrap	Repeats hide unique picks	Ex 1
B	Classification vote, clear majority	which trees count	Ex 2
C	Classification vote, tie	even $|S_i|$, no majority	Ex 3
D	Regression average	different aggregation rule	Ex 4
E	Full OOB error over all points	mixing per-point $S_i$	Ex 5
F	Degenerate: point OOB for zero trees	prediction undefined	Ex 6
G	Limiting: $n\to \infty$ vs small $n$	the $0.368$ number	Ex 7
H	Real-world word problem	translate story → OOB	Ex 8
I	Exam twist: OOB vs train error gap	why they differ	Ex 9

The blueprint below is the whole world our examples live in: rows are points, columns are trees, a cell is dark (in-bag) or amber (OOB). Everything else is bookkeeping on this grid.

---

Example 1 — Read the OOB set off a bootstrap (Cell A)

Forecast: guess how many of the 6 points ended up OOB before reading on.

1. List the distinct indices that appear. They are $\{1,4,6\}$. Why this step? A point is in-bag if it appears at least once; repeats ($4$ thrice, $1$ twice) don't add new points, so we collapse to the unique set.
2. OOB = everything not in that set: $\{2,3,5\}$. Why this step? By definition OOB means "never drawn". Points $2,3,5$ are absent, so the tree never saw them.
3. Fraction OOB: $3/6=0.5$. Why this step? Just count OOB over $n$.

Verify: in-bag $\cup$ OOB $=\{1,4,6\}\cup \{2,3,5\}=\{1,2,3,4,5,6\}$, and they're disjoint — every point is classified exactly once. ✓ Fraction $0.5$ here; for tiny $n$ the OOB fraction is noisy and only settles onto its long-run value for large $n$ — we derive that long-run value ($\approx 0.368$) carefully in Example 7, so don't worry where it comes from yet.

---

Example 2 — Classification, clear majority (Cell B)

Forecast: which label wins, and does it match $y_3$?

1. Count votes only inside $S_3$. Zeros: $T_1,T_7,T_8$ → three. Ones: $T_4,T_{12}$ → two. Why this step? Only trees that never trained on $x_3$ may vote — that keeps the estimate honest (no bagging label leakage).
2. Majority vote: $3>2\Rightarrow {\hat{y}}_3=0$. Why this step? Classification aggregation is the plurality of the sub-ensemble $S_3$.
3. Loss: $L(y_3,{\hat{y}}_3)=1[0\ne 0]=0$ (recall $1$ is $1$ if the inside is true, else $0$; here $0\ne 0$ is false). Why this step? 0/1 loss is $0$ when prediction matches truth.

Verify: $3+2=5=|S_3|$ — all OOB votes accounted for. Prediction $0$ equals $y_3=0$, so this point adds nothing to the error. ✓

---

Example 3 — Classification with a TIE (Cell C)

Forecast: two ones, two zeros — what does a forest actually do?

1. Count: ones $=2$, zeros $=2$. A genuine tie. Why this step? An even $|S_i|$ can split evenly — the case the naive "majority" rule doesn't cover.
2. Turn the 0/1 votes into a class-1 probability. Each tree votes a hard $0$ or $1$; the ensemble's estimated probability of class 1 is simply the fraction of trees voting 1 among $S_5$: ${\hat{p}}_1=\frac{\#\text{ones}}{|S_5|}=\frac{1+0+1+0}{4}=0.5$. Why this step? "Probability of class 1" is not mystical here — it is just how many of the qualifying trees said 1, divided by how many voted. Averaging the $0/1$ votes gives that fraction directly.
3. Apply the deterministic tie rule. The default rule predicts the class with the largest $\hat{p}$; at an exact tie ${\hat{p}}_1={\hat{p}}_0=0.5$ it returns the lower class index, so ${\hat{y}}_5=0$. Why this step? We must state a reproducible rule; scikit-learn's default is "argmax of averaged probabilities", and on an exact $0.5$ it returns the first class (index $0$).
4. Loss: $L(1,0)=1[1\ne 0]=1$. Why this step? 0/1 loss penalizes the mismatch fully.

Verify: ${\hat{p}}_1=0.5$ exactly ($2$ of $4$ votes are $1$), confirming a true tie; the deterministic rule gives a reproducible answer instead of a coin flip. ✓ (If your library breaks ties toward class 1, ${\hat{y}}_5=1$ and loss $=0$ — always know your library's rule.)

---

Example 4 — Regression average (Cell D)

Forecast: guess the averaged prediction to the nearest integer.

1. Average the OOB predictions. ${\hat{y}}_2=\frac{48+55+47+50}{4}=\frac{200}{4}=50$. Why this step? Regression aggregation is the mean over $S_i$, not a vote — trees output numbers, so we average.
2. Squared error: $(y_2-{\hat{y}}_2{)}^2=(50-50{)}^2=0$. Why this step? Squared-error loss is the standard regression loss $L(y,\hat{y})=(y-\hat{y}{)}^2$.

Verify: $48+55+47+50=200$, and $200/4=50$. The scatter around $50$ ($\pm 3,\pm 5$) cancels, giving a perfect hit — a nice reminder that averaging reduces variance (Bias-Variance Tradeoff). ✓

---

Example 5 — Full OOB error with per-point sub-ensembles (Cell E)

Forecast: how many of the 4 points get misclassified?

1. Point 1: ones $2$ vs zeros $1$ → ${\hat{y}}_1=1=y_1$ → loss $0$. Why this step? Point 1 is judged only by its own $S_1$ (3 trees); majority is $1$, matching $y_1$.
2. Point 2: zeros $3$ vs ones $1$ → ${\hat{y}}_2=0=y_2$ → loss $0$. Why this step? $S_2$ has 4 trees, a different set from $S_1$; the majority $0$ matches $y_2$.
3. Point 3: tie $\{0,1\}$ → lower-index rule → ${\hat{y}}_3=0\ne y_3=1$ → loss $1$. Why this step? $S_3$ has only 2 trees and splits evenly, so we fall back to the Example-3 tie rule (predict class $0$), which misses the truth.
4. Point 4: ones $2$ vs zeros $1$ → ${\hat{y}}_4=1\ne y_4=0$ → loss $1$. Why this step? $S_4$ (3 trees) votes majority $1$, but the truth is $0$ — an honest mistake this sub-ensemble makes.
5. Average: $\text{OOB error}=\frac{0+0+1+1}{4}=\frac{2}{4}=\mathrm{0.5.}$ Why divide by $n=4$? We average the per-point losses over all training points, each scored by its own $S_i$ — no shared hold-out.

Verify: two of four points wrong → $2/4=0.5$. ✓ Note each point used a different number of votes ($3,4,2,3$) — legitimate and typical.

---

Example 6 — Degenerate: a point OOB for NOBODY (Cell F)

Forecast: can we even predict this point with OOB rules?

1. Look at $S_1$. It is empty: no tree qualifies to vote. Why this step? OOB prediction is defined only over $|S_i|\ge 1$. With $|S_1|=0$ there is nothing to average or vote.
2. The prediction is undefined. Implementations either skip $x_1$ from the OOB error or emit a warning. Why this step? You cannot leak a label into the estimate, so you must exclude the point — it contributes $0$ terms to both numerator and denominator of the average.
3. Estimate how likely this is. The chance one tree leaves $x_1$ out is the exact finite-$n$ miss-probability ${\left(1-\frac{1}{n}\right)}^n$ (derived in Example 7). So the chance it is in-bag for one tree is $1-{\left(1-\frac{1}{n}\right)}^n$, and for all $B$ trees at once: $P(S_i=\varnothing )={\left(1-{\left(1-\frac{1}{n}\right)}^n\right)}^B.$ For a large dataset the inner term approaches its limit $1-e^{-1}\approx 0.632$, giving $P(S_i=\varnothing )\approx (0.632{)}^B$. For $B=3$ (and large $n$): $(0.632{)}^3\approx 0.252$ — a whopping 25% chance! For $B=100$: $(0.632{)}^{100}\approx 8\times 10^{-21}$ — vanishing. Why this step? We separate the exact finite-$n$ formula from its large-$n$ shortcut $0.632$, so you know the $0.632$ is an approximation valid when $n$ is big.

Verify: $0.632^3=0.2524\dots$ ✓ This is exactly the "OOB needs many trees" mistake from the parent: small $B$ leaves points undefined and estimates high-variance.

---

Example 7 — The limiting number, small vs large $n$ (Cell G)

Forecast: is the fraction increasing or decreasing toward $0.368$?

1. $n=5$: ${\left(1-\frac{1}{5}\right)}^5=(0.8{)}^5=0.32768$. Why this step? Direct plug-in of the exact miss-probability formula from the parent.
2. $n=100$: ${\left(0.99\right)}^{100}\approx 0.36603$. Why this step? Larger $n$ pushes toward the limit; still slightly above it.
3. $n\to \infty$: ${\left(1-\frac{1}{n}\right)}^n\to e^{-1}=0.367879\dots$ Why this step? This is the definition ${\lim }_{n\to \infty }{\left(1+\frac{x}{n}\right)}^n=e^x$ at $x=-1$ — the exponential is the tool that answers "what does repeated tiny multiplication converge to?"

How to read this figure: the horizontal axis is the dataset size $n$; the vertical axis is the OOB fraction ${\left(1-\frac{1}{n}\right)}^n$. The cyan curve plots that fraction as $n$ grows — it climbs steadily. The dashed amber line is the limit $e^{-1}\approx 0.3679$. The two white dots mark our computed values at $n=5$ ($0.3277$) and $n=100$ ($0.3660$). Read off the key message: the curve rises from below and flattens onto the amber line, so real datasets always have a little more than $37\%$ OOB when $n$ is small, converging down onto $e^{-1}$ as $n$ grows.

Verify: the sequence $0.32768,0.36603,\dots$ climbs monotonically toward $0.36788$ from below. ✓ So every real dataset has slightly more than 37% OOB for small $n$, converging down onto $e^{-1}$ as $n$ grows.

---

Example 8 — Real-world word problem (Cell H)

Forecast: guess how many of the 500 trees vote per customer.

1. OOB fraction per tree $={\left(1-\frac{1}{20000}\right)}^{20000}\approx e^{-1}=0.3679$. Why this step? $n=20,000$ is huge, so we use the limiting value.
2. Expected trees with the customer OOB: $0.3679\times 500\approx 184$ trees. Why this step? Each tree independently leaves the customer out with probability $0.3679$; expected count $=0.3679B$.
3. Trust argument: those $\approx 184$ trees never saw that customer, so their averaged vote is an honest test prediction. Doing this for all $20,000$ customers yields a test-error estimate for free during training — no extra model fits, unlike $k$-fold CV which refits $k$ times. Why this step? This is the core value proposition of OOB from the parent note.

Verify: $0.36788\times 500=183.9\approx 184$. ✓ And $P(\text{a customer OOB for zero trees})\approx 0.632^{500}\approx 0$, so no undefined predictions — large $B$ cures Cell F.

---

Example 9 — Exam twist: OOB vs training error (Cell I)

Forecast: which number is closer to real-world performance?

1. Training error uses ALL trees, including those that memorized each point. So a point $x_i$ is scored partly by trees that trained on it → optimistic → artificially low ($0.02$). Why this step? Decision trees can perfectly fit their bootstrap sample, so in-bag scoring leaks labels.
2. OOB error uses only $S_i$ (unseen trees). No leakage → honest → higher and realistic ($0.11$). Why this step? This is exactly why we restrict to $S_i$.
3. Conclusion: the model did not get worse; $0.11$ is the trustworthy test-error estimate. The gap $0.11-0.02=0.09$ is the optimism of training error. Why this step? OOB $\approx$ CV $\approx$ true test error; training error is a lower bound you should never quote.

Verify: gap $=0.09>0$ (OOB $\ge$ train for a well-fit forest). ✓ Reporting $0.02$ would over-promise; report $0.11$.

---

Recall One-line summary of the matrix

Guess the cell first ::: Identify OOB set (A) → aggregate by vote or mean over $S_i$ only (B/C/D) → average per-point losses (E) → watch empty $S_i$ (F) and the $e^{-1}$ limit (G) → translate stories (H) and never confuse OOB with train error (I).

---

Connections

• Bootstrap Sampling — creates the in-bag/OOB split every example reads off.
• Bootstrap Aggregating (Bagging) — the sub-ensemble $S_i$ is honest bagging on unseen data.
• Random Forests — the real consumer of OOB error (Ex 8).
• Cross-Validation — the paid alternative OOB replaces for free.
• Bias-Variance Tradeoff — averaging (Ex 4) cancels variance.
• Decision Trees — memorizing base learners cause the Ex 9 gap.