Bootstrap Resampling theory

Introduced by Bradley Efron in 1979, the bootstrap is a computer-intensive resampling methodology that approximates the unknown sampling distribution of an estimator θ̂ = T(F) by substituting the empirical distribution function F_n in place of the unknown population distribution F. Under the 'plug-in principle', properties of the estimator θ̂ under F (such as standard error, bias, and confidence intervals) are estimated by drawing repeated samples X* of size n with replacement from F_n and evaluating θ̂* = T(F_n*). The bootstrap requires no parametric assumptions and applies to virtually any estimator regardless of mathematical complexity.

The empirical distribution function F_n places discrete probability mass 1/n on each of the observed sample points {x_1, x_2, ..., x_n}. Drawing a sample of size n from F_n is mathematically identical to drawing n observations from the set {x_1, ..., x_n} with replacement, such that each point has equal selection probability 1/n on every draw. In any given bootstrap pseudo-sample, the probability that a specific original data point is selected at least once is 1 - (1 - 1/n)^n, which converges to 1 - 1/e ≈ 63.21% as n → ∞. Thus, approximately 63.2% of the original observations appear in a bootstrap sample, while 36.8% are omitted (the 'out-of-bag' samples).

To construct a (1 - 2α) percentile confidence interval, generate B independent bootstrap replicates θ̂*_1, θ̂*_2, ..., θ̂*_B and sort them in ascending order: θ̂*_{(1)} ≤ θ̂*_{(2)} ≤ ... ≤ θ̂*_{(B)}. The lower confidence limit is set to the empirical α-quantile θ̂*_{(⌊B α⌋)}, and the upper limit is set to the (1 - α)-quantile θ̂*_{(⌊B (1 - α)⌋)}. For example, with B = 2,000 replicates and α = 0.025 (95% confidence interval), the limits are given by the 50th and 1,950th ordered bootstrap replicates. Percentile intervals are transformation-invariant: for any monotonic transformation g, the interval for g(θ) is [g(L), g(U)].

The basic percentile interval is first-order accurate: its coverage error is O(1/√n), and it can suffer from substantial undercoverage when the sampling distribution is skewed or when the estimator is biased. Efron (1987) introduced the Bias-Corrected and Accelerated (BCa) interval, which achieves second-order accuracy O(1/n). The BCa method adjusts the percentile endpoints using two parameters: (1) the bias-correction parameter z_0 = Φ^(-1)(#{θ̂*_b < θ̂} / B), which accounts for median bias; and (2) the acceleration parameter a, computed from jackknife influence values, which accounts for the rate of change of the estimator's standard error with respect to the true parameter.

Efron and Tibshirani demonstrated that estimating the bootstrap standard error SE_boot requires only moderate replication: B = 50 to 200 replications typically suffices, because the standard error of a variance estimate stabilizes quickly. However, constructing accurate 95% percentile or BCa confidence intervals requires estimating extreme tail quantiles (2.5% and 97.5%). Estimating tail quantiles with high precision requires substantially more resamples: B ≥ 1,000 to 2,000 replications is standard practice. For testing significance at α = 0.01, B ≥ 5,000 or 10,000 is recommended.

The bootstrap fails when the empirical distribution F_n does not provide a smooth approximation to F. For the sample maximum X_{(n)} = max(X_1, ..., X_n), the maximum of a bootstrap sample X* can never exceed the observed sample maximum: P(X*_{(n)} ≤ X_{(n)}) = 1.0. In fact, the probability that the bootstrap maximum equals the observed maximum is exactly 1 - (1 - 1/n)^n ≈ 1 - 1/e ≈ 63.2%. Thus, the bootstrap distribution of the maximum has a discrete probability mass of 63.2% at a single point, whereas the true distribution of the maximum is continuous. In such extreme cases, subsampling (the m-out-of-n bootstrap where m ≪ n) must be used.

Let q_α be the true α-quantile of the bootstrap distribution. The empirical bootstrap quantile q̂_α is estimated from a finite sample of B independent Monte Carlo replicates. By the asymptotic distribution of sample quantiles, the Monte Carlo standard error of q̂_α is given by MCSE(q̂_α) = √[α(1 - α)] / [f_B(q_α) √B] ∝ B^(-1/2). Taking natural logarithms yields ln(MCSE) = -0.5000 ln(B) + C. This confirms that simulation error decays at the standard Monte Carlo square-root rate, requiring a 4-fold increase in B to halve simulation uncertainty.