Out-of-bag error estimation: Visual walkthrough

This page draws the one number that makes OOB error work: why about $37%$ of your data is "left out" of every tree. We build it picture by picture, touching no symbol before it earns its place.

We are studying bootstrap sampling — the with-replacement draw that bagging and random forests are built on. The whole magic reduces to a single question:

If I pull a name out of a hat $n$ times (putting it back each time), what is the chance one particular name never comes out?

Answer that, and you understand where OOB samples come from.

Step 1 — The dataset is a bag of numbered balls

WHAT. Picture your training set as a physical bag. Every training point is one ball, painted with a number: ball $1$ , ball $2$ , up to ball $n$ . Here $n$ (say it "en") is just the number of training points — the count of rows in your data.

WHY start here. A bootstrap sample is literally drawing balls from this bag. If we can see the bag, we can see the drawing, and the whole probability becomes counting.

PICTURE. Look at the bag below: $n = 5$ balls, each equally likely to be grabbed. The dashed arrow is your hand reaching in.

Step 2 — One draw: the chance of missing ball $i$

WHAT. Fix your eye on one specific ball — call it ball $i$ (the $i$ -th point). In a single grab, what is the chance you do not pull ball $i$ ?

WHY this tool — simple counting of equally likely outcomes. Every ball is equally likely, so probability is just favourable outcomes over total outcomes. There are $n$ balls total, and $n - 1$ of them are "not ball $i$ ". No calculus needed yet — just fractions.

P (miss i in one draw) = (not- i balls) / (all balls) \frac{n - 1}{n} = 1 - \frac{1}{n}

Term by term: the top $n - 1$ counts every ball except $i$ ; the bottom $n$ counts all balls; their ratio is the fraction of the bag that is "safe" from being $i$ . Rewriting $\frac{n - 1}{n}$ as $1 - \frac{1}{n}$ just says "the whole bag ( $1$ ) minus ball $i$ 's share ( $\frac{1}{n}$ )."

PICTURE. The pie shows the bag split into ball $i$ 's slice (pink, $\frac{1}{5}$ ) and the "miss" region (blue, $\frac{4}{5}$ ). One grab landing anywhere in blue is a miss.

Step 3 — All $n$ draws: multiply the misses

WHAT. A bootstrap sample is not one grab — it is $n$ grabs, putting the ball back each time. Ball $i$ is out-of-bag only if it is missed on grab 1 and grab 2 and ... and grab $n$ .

WHY multiplication — independence. Because we replace the ball after every grab, the bag is identical for every draw. Independent "and" events combine by multiplying their probabilities. That is the only reason we get a clean power here.

P (i is OOB) = miss grab 1 (1 - \frac{1}{n}) \times \dots \times miss grab n (1 - \frac{1}{n}) = (1 - \frac{1}{n})^{n}

Term by term: each bracket is the same one-draw miss chance from Step 2 (identical bag every time). The exponent $n$ counts how many grabs must all be misses. "With replacement" is exactly what makes all $n$ brackets equal.

PICTURE. A ladder of $n$ independent grabs; each rung multiplies in another $(1 - \frac{1}{n})$ . Ball $i$ survives to the bottom only if every rung is a miss.

Step 4 — Watch the number settle as the bag grows

WHAT. Plug in growing $n$ and watch $(1 - \frac{1}{n})^{n}$ :

n 125101001000 (1 - \frac{1}{n})^{n} 0 0.25 0.328 0.349 0.366 0.3677

WHY it doesn't just go to zero. Two forces fight: the base $1 - \frac{1}{n}$ creeps up toward $1$ (each miss gets easier), while the exponent $n$ grows (more grabs to survive). They balance, and the product homes in on a fixed value near $0.368$ — not $0$ , not $1$ .

PICTURE. The curve of $(1 - \frac{1}{n})^{n}$ against $n$ , flattening onto a dashed horizontal line. The tug-of-war is visible: it plunges from $n = 1$ then bends and levels off.

Step 5 — Name the limit: it's $e^{- 1}$

WHAT. The value the curve settles on is exactly $e^{- 1}$ , where $e \approx 2.71828$ is Euler's number.

WHY $e$ appears — it is the definition of $e$ . The number $e$ is defined by the fact that $(1 + \frac{x}{n})^{n}$ approaches $e^{x}$ as $n$ grows. Our expression is that pattern with $x = - 1$ :

n \to \infty lim (1 + \frac{x}{n})^{n} = e^{x} x = - 1 n \to \infty lim (1 - \frac{1}{n})^{n} = e^{- 1} \approx 0.3679

Term by term: $x$ is the "per-step nudge" ( $- 1$ here, because each grab subtracts one ball's share $\frac{1}{n}$ ); $n$ is the number of steps; the limit turns "many tiny multiplicative nudges" into a single exponential. We reach for the exponential precisely because it is the one function that collapses an $n$ -fold product of near- $1$ factors into a closed number.

PICTURE. Same curve as Step 4, now with the dashed line labelled $e^{- 1} \approx 0.368$ and the $63.2%$ in-bag remainder shaded above it.

Step 6 — Edge cases: don't skip the ends

Limits are honest only if the boundaries behave. Check every corner.

$n = 1$ . One ball, one grab — you always pick it. $(1 - \frac{1}{1})^{1} = 0^{1} = 0$ . Chance of OOB is $0$ : with a single point, nothing is ever left out. ✔ matches the table.

$n = 2$ . $(1 - \frac{1}{2})^{2} = (\frac{1}{2})^{2} = 0.25$ . Already sensible — a full quarter of the time the point is missed both grabs.

Small $n$ in practice. For $n = 5$ we got $0.328$ , and Worked Example 1 in the parent measured $0.40$ on one actual sample. Both are fine: the $e^{- 1}$ value is the long-run average, and any single tree's OOB fraction rattles around it. Small $n$ $\Rightarrow$ more rattle.

$n \to \infty$ . The limit $e^{- 1}$ ; the fraction stops moving. This is the regime real datasets live in, which is why " $37%$ OOB" is a safe rule of thumb.

PICTURE. A number line from $0$ to $1$ with the sequence's values dropped as ticks — $n = 1$ at $0$ , then climbing to $0.25, 0.328, \dots$ and crowding just under the pale-yellow $e^{- 1}$ mark.

Step 7 — From " $37%$ " to a usable test set

WHAT. Turn the probability into the payoff. If a point is OOB for a tree with chance $\approx 0.37$ , then across $B$ trees it is OOB for about $0.37 B$ of them — a ready-made mini test panel of trees that never saw it.

WHY this closes the loop. OOB error predicts each point using only those $\approx 0.37 B$ un-trained trees (majority vote for classification, average for regression), then averages the loss. The $37%$ we just derived is precisely what guarantees every point has enough "honest" judges — provided $B$ is large.

E [# trees where x_{i} is OOB] \approx 0.368 B

Term by term: $B$ is the total number of trees; $0.368$ is our $e^{- 1}$ ; their product is the expected size of the honest sub-ensemble $S_{i}$ that votes on point $x_{i}$ .

PICTURE. A row of $B$ trees; for one highlighted point, the blue-tinted trees ( $\approx 37%$ ) are its OOB voters, the faded ones trained on it and are ignored.

The one-picture summary

Everything in one frame: bag $\to$ one-draw miss $\to$ multiply over $n$ grabs $\to$ curve settles $\to$ $e^{- 1} \approx 0.368$ OOB, $0.632$ in-bag $\to$ honest voters per point.

Recall Feynman: the whole walkthrough in plain words

Put every training point as a numbered ball in a bag. To build one tree you grab a ball, write it down, and drop it back, over and over, $n$ times. Pick one ball and ask: what's the chance it never gets grabbed? In one grab, missing it is easy — $1 - \frac{1}{n}$ . But you grab $n$ times, and because you keep dropping the ball back, each grab is the same fresh chance, so you multiply: $(1 - \frac{1}{n})^{n}$ . As the bag gets huge, missing any one ball gets easier ( $1 - \frac{1}{n} \to 1$ ) but there are more grabs to survive ( $n$ up) — the two pushes balance and the number stops at about $0.368$ , which is $e^{- 1}$ , the very number that defines $e$ . So roughly $37%$ of points sit outside each tree's training. Those "left-out" points are a free test set: quiz each point using only the trees that never studied it, average the mistakes, and you get an honest estimate of how the forest handles new data — no separate validation set required.

Connections

Bootstrap Sampling — the with-replacement grab this whole page counts.
Bootstrap Aggregating (Bagging) — where the leftover $37%$ becomes free validation data.
Random Forests — the ensemble that consumes the derived OOB fraction.
Cross-Validation — the alternative estimate OOB cheaply mimics.
Bias-Variance Tradeoff — averaging many trees is why OOB tracks test error.
Decision Trees — the base learners doing the voting.
Hinglish version →