Bootstrap & Resampling — Uncertainty for Arbitrary Statistics

Classical statistics hands you a formula for the standard error of the sample mean (SE = σ/√n) and the sample proportion, but the moment you ask about the median, the 90th percentile, an NDCG score, a Gini coefficient, or the ratio of two means, the closed-form derivations collapse. Before 1979, applied statisticians would either invoke asymptotic approximations that held only for huge n, or they would punt.

Efron's bootstrap (1979) fixed this in one move: if you cannot derive the sampling distribution analytically, simulate it by resampling the data you already have. The key conceptual leap is the plug-in principle — treat the empirical distribution F̂ (the histogram of your sample) as a stand-in for the true distribution F. Draw B new samples of size n from F̂ with replacement, compute your statistic θ̂* on each, and the resulting B values approximate the true sampling distribution of θ̂.

The misconception that sinks candidates: "Bootstrap gives you more data." It does not. You have the same n observations — the bootstrap just extracts every drop of information about variability that those n points can give you. The uncertainty you estimate is a lower bound on your actual uncertainty, not a substitute for collecting more data.

The mathematical core: we want the sampling distribution of θ̂ = T(X₁,...,Xₙ) where Xᵢ ~ F. We do not know F, but we have X₁,...,Xₙ. The empirical distribution F̂ₙ places mass 1/n on each observed point. By the Glivenko-Cantelli theorem, F̂ₙ → F uniformly as n → ∞, so for smooth functionals T, T(F̂ₙ) → T(F).

The bootstrap step: draw X₁*,...,Xₙ* i.i.d. from F̂ₙ (equivalent to sampling with replacement from the original data). Compute θ̂* = T(X₁*,...,Xₙ*). Repeat B times. The distribution of {θ̂₁,...,θ̂_B} approximates the distribution of θ̂ centered around θ.

The bootstrap principle: the distribution of θ̂* − θ̂ (the bootstrapped statistic minus the plug-in estimator) approximates the distribution of θ̂ − θ (the estimator minus the true parameter). This is what makes bootstrap CIs valid — we use the bootstrap distribution of deviations, not the raw bootstrap distribution, to reason about where the true θ lies.

Bickel-Freedman (1981) proved consistency for the mean and many smooth functionals. The conditions that matter: finite variance, smoothness of T as a functional of F, and i.i.d. sampling. Violate any of these and the bootstrap can silently produce wrong CIs.

Non-parametric bootstrap (the default) resamples directly from F̂ₙ. It makes no assumptions about the functional form of F. This is what 95% of production use cases need — ratio metrics, quantile metrics, ranking metrics.

Parametric bootstrap fits a parametric model (say, Normal(μ̂, σ̂²)) to the data, then draws B samples from the fitted model rather than resampling the raw observations. Use it when: (1) sample size is small (n < 30) and you have strong prior belief in the distributional family; (2) you need to bootstrap a statistic that depends on tail behavior the raw sample cannot express (e.g., the 99.9th percentile from n=500); (3) you want smoother bootstrap distributions for pivotal statistics.

Trade-off: parametric bootstrap is more efficient when the model is correct but badly misleading when the model is wrong — model misspecification propagates directly into the CI. Non-parametric is safer by default. A common hybrid at Stripe and Netflix: non-parametric bootstrap for business metrics, parametric for small-cell analyses where non-parametric has too few unique resamples.

Bootstrap is not universal. The four failure modes below are common interview traps.

1. Extremes and order statistics. If θ = max(X), the bootstrap estimate max(X*) can never exceed max(X) — every resample is drawn from the original sample. The bootstrap distribution has a point mass at the true max with high probability, grossly underestimating variance. Frangos-Schucany (1990) formalized this. Fix: extreme value theory (GEV distributions) or subsampling.

2. Dependent data. I.i.d. bootstrap destroys autocorrelation. Apply it to time-series and your SEs will be dramatically too small. Fix: moving block bootstrap (Kunsch 1989) resamples contiguous blocks of length ℓ, preserving local dependence. Stationary bootstrap (Politis-Romano 1994) uses random block lengths from a geometric distribution. Block length ℓ ≈ n^(1/3) is a starting heuristic; Politis-Romano provides a data-driven procedure.

3. Very small samples (n < 10). With n = 5, there are only C(9,5) = 126 distinct bootstrap samples. The bootstrap distribution is discrete and coarse. Use exact methods (permutation, Fisher's exact) or parametric bootstrap.

4. Heavy tails with infinite variance. For Pareto-like distributions with shape α < 2, the variance is infinite and the CLT does not apply. Bootstrap CIs for the mean have incorrect coverage. Fix: log-transform, trimmed means, or m-out-of-n subsampling.

Bootstrap CIs and permutation tests are often confused. They answer different questions.

Bootstrap estimates the sampling distribution of a statistic given the data. It is about uncertainty of the estimate and natively produces CIs.

Permutation test directly tests a null hypothesis of exchangeability — under H₀, the group labels are irrelevant, so any permutation of labels is equally likely. Shuffle the labels, recompute the statistic, and the fraction of permutations with statistic ≥ observed gives the p-value. This is exact: no asymptotics, no distributional assumptions, valid at any sample size.

When to use permutation over bootstrap for testing: always, for two-sample mean differences, correlations, regression coefficients, and any two-group comparison. Bootstrap "tests" (e.g., check if 0 is in the bootstrap CI of θ̂₁ − θ̂₂) have subtly wrong Type I error under H₀ because the bootstrap distribution is centered around the observed difference, not around 0.

Limitation of permutation tests: they require exchangeability. If treatment has heterogeneous variance (e.g., unequal-variance Welch case), the vanilla permutation test loses validity — use studentized statistics or the Janssen-Pauls modification.

The bootstrap is not just a statistical tool — it is the foundation of major ML methods.

Bagging (Breiman 1996) — "bootstrap aggregating" — trains B models on B bootstrap samples of the training data and averages predictions. Each bootstrap sample contains ~63.2% of the training data, leaving ~36.8% as out-of-bag (OOB) samples for free, unbiased error estimation without a separate validation set. Random forests are bagging + random feature subsets at each split. For B = 500 trees, OOB error closely approximates 10-fold CV error at a fraction of the cost.

.632+ estimator (Efron 1997) generalizes OOB. Naive OOB is slightly pessimistic (trains on 63.2% of data); .632+ combines training error and OOB error with data-dependent weights to de-bias, and is the theoretically preferred small-n alternative to CV.

Uncertainty quantification for ML. Bootstrap the training set → train B models → get a distribution over predictions at each test point. Practical for linear models, trees, and small neural nets. For deep learning, the bootstrap is prohibitively expensive, but deep ensembles (Lakshminarayanan et al., 2017) — training B networks from different random initializations on the same data — emerged as the DL analog and remain the strongest baseline for uncertainty estimation, outperforming MC-Dropout and variational methods in most benchmarks.

Bootstrap CIs for ML metrics (AUC, precision@k, NDCG@10) are the standard approach — no closed-form SE exists for most ranking metrics, so bootstrap the test set and recompute.

Jackknife (Quenouille 1949, Tukey) predates the bootstrap by 30 years. For each i ∈ {1,...,n}, compute θ̂₍ᵢ₎ = T(X₋ᵢ) — the statistic with the i-th observation removed. The jackknife SE and bias estimators use these n leave-one-out replicates.

Advantages: only n computations (cheaper than B=10,000 bootstrap). Produces the acceleration parameter a in BCa via the third-moment formula. Historically the go-to bias-correction method.

Disadvantages: less efficient than bootstrap; fails catastrophically for non-smooth statistics like the median when n is even (the median jumps discontinuously as points are removed, breaking the smoothness required for consistency). For any modern application, prefer the bootstrap — jackknife's main role today is computing BCa's acceleration and out-of-bag error in random forests.

Netflix uses bootstrap for CIs on ranking metrics (NDCG, MRR) in offline experimentation, and for revenue-per-user CIs where the long-tail of subscription revenue violates t-test assumptions. Block bootstrap handles autocorrelated engagement metrics.

Stripe uses bootstrap for A/B test CIs on payment success rates by merchant segment (heavy-tailed transaction volume) and for ratio metrics like authorization rate per attempt, where the numerator and denominator are correlated and no closed-form SE exists.

Uber, DoorDash, LinkedIn apply cluster bootstrap at the user or city level to avoid the within-user correlation trap for metrics like bookings-per-session or jobs-viewed-per-visit.

General patterns: (1) bootstrap for all ratio metrics; (2) cluster bootstrap when the randomization unit is not the measurement unit; (3) block bootstrap for intraday seasonality or autocorrelated metrics; (4) permutation tests for hypothesis testing on any custom metric without a standard test; (5) B = 10,000 as the default for production CIs, computed asynchronously via Spark or Ray if the statistic is expensive.