Bootstrap and resampling

The idea

Classical inference hands you standard-error formulas for a few blessed statistics — means, proportions, regression coefficients. The moment you care about a median, a ratio of two metrics, an AUC, or a p90, the formula book runs out. The bootstrap replaces the formula book with compute:

1. From your sample of $n$ observations, draw $n$ observations with replacement (some rows repeat, others drop out).
2. Compute your statistic on the resample.
3. Repeat $B$ times ($B \approx 1000$ to $10{,}000$). The distribution of the $B$ values approximates the sampling distribution of the statistic.

From there: the SD of the $B$ values is the bootstrap standard error; the 2.5th and 97.5th percentiles form the 95% percentile interval.

Why this is legitimate and not a free lunch: the plug-in principle. The true sampling distribution comes from repeatedly sampling the population; we cannot do that, so we substitute the best available estimate of the population — the empirical distribution of the sample itself — and sample from that instead. The approximation is good exactly to the extent that the sample resembles the population. The bootstrap quantifies uncertainty; it manufactures no new information, and it faithfully reproduces any bias your sample already has.

A detail interviewers probe: resamples must be size $n$, with replacement. Sampling noise depends on $n$, so simulating at a different size measures the wrong thing — and without replacement at size $n$ you would get the original sample back every time, showing zero variance. Each resample leaves out about $(1 - 1/n)^n \approx e^{-1} \approx 36.8\%$ of observations — the same "out-of-bag" fraction that bagging exploits for free validation.

Its cousin, the permutation test, shuffles group labels instead: it simulates the null world ("labels do not matter") to get a p-value, whereas the bootstrap simulates the sampling process to get SEs and CIs. Both are "resampling methods"; they answer different questions.

Worked example

Ten measured API latencies (ms), sorted:

$12, \; 15, \; 21, \; 30, \; 45, \; 51, \; 62, \; 80, \; 110, \; 350$

Sample median $= (45 + 51)/2 = 48$ ms. The 350 is real (a retry storm), so you want the median and honest uncertainty — but there is no $s/\sqrt{n}$ formula for medians.

Bootstrap by hand for two resamples (indices drawn with replacement):

Run $B = 10{,}000$ of these and collect the medians. A typical run concentrates on the achievable values (30, 37.5, 45, 48, 51, 56.5, 62, ...) with a 95% percentile interval of roughly $(21, 80)$ ms. Notice what the bootstrap did automatically: the interval is asymmetric — wider above than below — because the data is right-skewed, something $\pm 1.96 \times \text{SE}$ symmetry could never express. Also visible: with $n = 10$ the bootstrap distribution is lumpy (medians of resamples can only hit averages of pairs of observed values) — a candid illustration that the bootstrap cannot conjure resolution the sample does not contain.

Cheat sheet

• Procedure: resample $n$ with replacement → recompute statistic → repeat $B \geq 1000$ → SE = SD of replicates; 95% CI = 2.5th-97.5th percentiles.
• Plug-in principle: empirical distribution stands in for the population; quality of the stand-in bounds quality of everything downstream.
• Out-of-bag fraction: each resample omits $\approx e^{-1} \approx 36.8\%$ of rows.
• Percentile CI is the default; BCa (bias-corrected accelerated) improves coverage for skewed statistics at no conceptual cost.

Gotchas:

• Resample the randomization unit (user), not the row (event/session), when rows are dependent.
• $B$ only controls simulation noise; the original $n$ controls real precision. $B = 10{,}000$ on $n = 20$ is still an $n = 20$ answer.
• Bootstrap ≠ permutation: bootstrap → CI/SE around an estimate; permutation → p-value under a no-effect null.
• For plain means at large $n$, bootstrap and CLT formulas agree — use the formula; bootstrap earns its cost on everything else.