Out-of-bag error estimation: Exercises — AI-ML deep dive

Ten problems, easy to hard. Every one has a full solution hidden inside a collapsible callout — read the problem, try it, then expand. Levels run L1 Recognition → L2 Application → L3 Analysis → L4 Synthesis → L5 Mastery.

This page drills the ideas built in the parent note: the 63/37 split from Bootstrap Sampling, the honest sub-ensemble used to score each point, and how OOB compares to Cross-Validation as a generalization estimate for Random Forests.

Before we start, here is the one picture the whole page leans on: what "in-bag" and "out-of-bag" actually mean for a single tree.

The bag on the left holds the $n$ original points. A bootstrap sample (right) is drawn by reaching in $n$ times, putting the point back each time (with replacement). Points that got drawn at least once are in-bag (violet) — the tree trains on them. Points never drawn are out-of-bag (orange) — the tree never sees them, so they can honestly test it.

Level 1 — Recognition

Exercise 1.1

Dataset indices ${1, 2, 3, 4, 5, 6}$ ( $n = 6$ ). A tree's bootstrap sample is ${3, 1, 3, 6, 1, 3}$ . List the in-bag set and the out-of-bag (OOB) set for this tree.

Recall Solution

In-bag = the unique indices that appear at least once. Scanning ${3, 1, 3, 6, 1, 3}$ : the values present are $1, 3, 6$ . So in-bag $= {1, 3, 6}$ . OOB = every original index not in that list. From ${1, 2, 3, 4, 5, 6}$ , remove ${1, 3, 6}$ → OOB $= {2, 4, 5}$ . Sanity check: in-bag ( $3$ ) + OOB ( $3$ ) $= 6 = n$ . ✓ Every point is exactly one of the two.

Exercise 1.2

True or false: "A point that is drawn twice in a bootstrap sample is out-of-bag." Explain in one sentence.

Recall Solution

False. Out-of-bag means drawn zero times. Being drawn twice still means the tree trained on that point (it just weighted it more heavily), so it is firmly in-bag. OOB is about absence, not count.

Level 2 — Application

Exercise 2.1

For $n = 10$ , compute the exact probability that a specific point $i$ is OOB for one tree, and compare it to the large- $n$ limit $e^{- 1}$ .

Recall Solution

Probability of missing point $i$ in one draw is $1 - \frac{1}{10} = 0.9$ (the draw lands on one of the other $9$ points). Draws are independent, so missing it in all $10$ draws: $P (OOB) = (1 - \frac{1}{10})^{10} = 0. 9^{10} \approx 0.3487.$ Compare to $e^{- 1} \approx 0.3679$ . Already within $2$ percentage points at $n = 10$ — the limit converges fast.

Exercise 2.2

Binary classification. Point $x_{4}$ has true label $y_{4} = 0$ . It is OOB for trees ${T_{1}, T_{3}, T_{6}, T_{8}, T_{10}}$ with predictions $T_{1} = 0, T_{3} = 1, T_{6} = 0, T_{8} = 0, T_{10} = 1.$ Give the OOB prediction $\overset{y}{^}_{4}$ and its 0/1 loss.

Recall Solution

Aggregate only these five OOB trees (ignore all trees that trained on $x_{4}$ ). Votes: three $0$ 's ( $T_{1}, T_{6}, T_{8}$ ) vs two $1$ 's ( $T_{3}, T_{10}$ ). Majority = $0$ , so $\overset{y}{^}_{4} = 0$ . Since $\overset{y}{^}_{4} = 0 = y_{4}$ , the 0/1 loss $L (y_{4}, \overset{y}{^}_{4}) = 0$ (correct → contributes nothing to the error).

Level 3 — Analysis

Exercise 3.1

Regression, $n = 4$ , squared-error loss. OOB predictions:

$i$	$y_{i}$	$\overset{y}{^}_{i}$
1	5	6
2	8	8
3	12	9
4	20	22

Compute the OOB mean squared error (MSE).

Recall Solution

Per-point squared errors $(y_{i} - \overset{y}{^}_{i})^{2}$ :

$i = 1 : (5 - 6)^{2} = 1$
$i = 2 : (8 - 8)^{2} = 0$
$i = 3 : (12 - 9)^{2} = 9$
$i = 4 : (20 - 22)^{2} = 4$

Sum $= 1 + 0 + 9 + 4 = 14$ . Average over all $n = 4$ points: $OOB MSE = \frac{14}{4} = 3.5.$ We divide by $4$ , not by "number of trees" — OOB error is an average over training points, each scored by its own OOB sub-ensemble.

Exercise 3.2

A forest has $B = 50$ trees. Roughly how many trees is a given point OOB for, on average? If a point turns out to be OOB for only $3$ trees, why is its OOB prediction untrustworthy?

Recall Solution

Each tree independently leaves a point out with probability $\approx e^{- 1} \approx 0.368$ . Across $B = 50$ trees the expected number of OOB trees is $0.368 \times 50 \approx 18.4 trees .$ A point with only $3$ OOB trees is in the unlucky tail. Its prediction is a vote/average over just $3$ estimators, which is high variance — one weak tree can flip a majority vote, and the squared-error average is noisy. With enough trees ( $B$ large) this per-point count grows and the estimate stabilizes.

Level 4 — Synthesis

Exercise 4.1

As $n \to \infty$ the OOB fraction is $e^{- 1} \approx 0.368$ . But at small $n$ it differs. Compute the exact OOB probability for $n = 2$ and $n = 3$ , and state whether the fraction increases or decreases toward the limit as $n$ grows.

Recall Solution

Use $P (OOB) = (1 - \frac{1}{n})^{n}$ .

$n = 2 : (1 - \frac{1}{2})^{2} = 0. 5^{2} = 0.25.$
$n = 3 : (1 - \frac{1}{3})^{3} = (\frac{2}{3})^{3} = \frac{8}{27} \approx 0.2963.$

Values: $0.25, 0.296, \dots \to 0.368$ . The sequence increases monotonically toward $e^{- 1}$ from below. So small datasets have fewer OOB points per tree than the famous $37%$ .

The orange curve is $(1 - 1/ n)^{n}$ climbing toward the navy dashed line $e^{- 1}$ . Notice how quickly it flattens — by $n \approx 20$ you are essentially at the limit, which is why the " $37%$ " rule of thumb is safe for any real dataset.

Exercise 4.2

You train a Random Forest and observe: training error $= 0.00$ , OOB error $= 0.14$ , 10-fold CV error $= 0.15$ . Interpret each number and explain why training error is so much lower than the other two.

Recall Solution

Training error $0.00$ : each point is scored partly by trees that memorized it (it was in-bag for ~ $63%$ of trees). Those trees reproduce the label perfectly → optimistically zero. This measures fit, not generalization.
OOB error $0.14$ : each point is scored only by trees that never saw it → an honest out-of-sample estimate. This tracks test error.
CV error $0.15$ : an independent generalization estimate from refitting on folds. It agrees with OOB ( $0.14 \approx 0.15$ ), which is the expected behavior for bagged models.

The gap ( $0.00$ vs $0.14$ ) is exactly the label leakage of training error. OOB $\approx$ CV confirms the model generalizes to about $14$ – $15%$ error, and OOB got there for free during training.

Level 5 — Mastery

Exercise 5.1

A dataset has $n = 5$ points. You build $B = 4$ trees with these bootstrap samples:

Tree	Bootstrap sample
$T_{1}$	${1, 2, 2, 4, 5}$
$T_{2}$	${1, 1, 3, 3, 5}$
$T_{3}$	${2, 3, 4, 4, 5}$
$T_{4}$	${1, 2, 3, 3, 3}$

For each point, list which trees have it OOB. Then flag any point whose OOB prediction would be undefined.

Recall Solution

First find each tree's in-bag (unique) set:

$T_{1}$ in-bag ${1, 2, 4, 5}$ → OOB ${3}$
$T_{2}$ in-bag ${1, 3, 5}$ → OOB ${2, 4}$
$T_{3}$ in-bag ${2, 3, 4, 5}$ → OOB ${1}$
$T_{4}$ in-bag ${1, 2, 3}$ → OOB ${4, 5}$

Now invert — for each point, collect the trees that have it OOB:

Point $1$ : OOB in ${T_{3}}$
Point $2$ : OOB in ${T_{2}}$
Point $3$ : OOB in ${T_{1}}$
Point $4$ : OOB in ${T_{2}, T_{4}}$
Point $5$ : OOB in ${T_{4}}$

Every point has $\geq 1$ OOB tree, so no prediction is undefined here — but points $1, 2, 3, 5$ rest on a single tree's vote each (very high variance). Only point $4$ gets two votes. This is exactly why OOB needs large $B$ : with $B = 4$ most points are barely covered.

Exercise 5.2

Show algebraically that the per-draw miss probability $1 - \frac{1}{n}$ raised to the $n$ -th power decreases toward $e^{- 1}$ from above for... wait — check the direction. Using $n = 1$ and $n = 2$ , determine whether $(1 - 1/ n)^{n}$ approaches $e^{- 1}$ from above or below, and reconcile with Exercise 4.1.

Recall Solution

Evaluate the endpoints:

$n = 1 : (1 - 1)^{1} = 0.$
$n = 2 : 0.25.$
$n = 3 : 0.296.$
Limit: $0.368.$

The sequence is $0, 0.25, 0.296, \dots \to 0.368$ : strictly increasing, approaching $e^{- 1}$ from below. So the claim "from above" is false — it converges from below. This matches Exercise 4.1. (Note: it is $(1 + \frac{1}{n})^{n}$ that approaches $e$ from below too, while $(1 - \frac{1}{n})^{- n}$ approaches $e$ from above — sign of the exponent flips the direction.)

Exercise 5.3 — capstone

You have $n = 1000$ and $B = 200$ trees. Estimate (a) the fraction of points OOB per tree, (b) the expected number of OOB trees per point, and (c) the expected number of points that are OOB for zero trees (undefined predictions). Use $p = e^{- 1}$ .

Recall Solution

(a) OOB fraction per tree $\approx e^{- 1} \approx 0.368$ (since $n = 1000$ is huge, we're at the limit). (b) Each point is OOB for a tree with prob $p = 0.368$ , independently across $B = 200$ trees: $E [OOB trees per point] = pB = 0.368 \times 200 = 73.6.$ (c) A point is OOB for zero trees with probability $(1 - p)^{B} = (0.632)^{200}$ . That number is astronomically small ( $\approx 1 0^{- 40}$ ). Expected count of such points $= 1000 \times (0.632)^{200} \approx 0$ .

Takeaway: with $B = 200$ and healthy $n$ , essentially every point gets ~ $74$ honest OOB votes → the OOB estimate is stable and trustworthy. The "undefined prediction" worry only bites at tiny $B$ .

Connections

Bootstrap Sampling — the with-replacement draw behind every "who's OOB?" exercise.
Bootstrap Aggregating (Bagging) — OOB falls out of bagging for free.
Random Forests — the ensemble consuming these OOB scores.
Cross-Validation — the estimate OOB is compared against in Exercise 4.2.
Bias-Variance Tradeoff — why small $B$ gives high-variance OOB (L3, L5).
Decision Trees — the base learners casting the votes.