Bootstrapping (Statistics)

In mathematical statistics and data science, bootstrapping is a computer-intensive resampling methodology that estimates the sampling distribution, variance, bias, and confidence intervals of a sample statistic (θ̂) by repeatedly drawing random samples with replacement from the observed empirical dataset itself. Formulated by American statistician Bradley Efron in 1979 as a generalization of the Quenouille–Tukey jackknife, the bootstrap replaces restrictive analytical assumptions (such as Gaussian normality or closed-form Taylor expansions) with direct Monte Carlo simulation.

Because the bootstrap treats the observed sample X = {x₁, x₂, ..., x_n} as a finite population that approximates the unknown true data-generating probability distribution F, it quantifies uncertainty for non-linear estimators—including medians, trimmed means, eigenvalues in principal component analysis, machine-learning ensemble trees (bagging), and clade topologies in molecular phylogenetics (introduced by Joseph Felsenstein in 1985).

The Empirical Distribution Function (F̂_n) and Replacement Combinatorics

In frequentist inference, an observed dataset x = (x₁, ..., x_n) consists of n independent and identically distributed (i.i.d.) draws from an unknown distribution F. A parameter θ = T(F) is estimated via the plug-in principle on the empirical distribution function (F̂_n), which assigns mass 1/n to each point: θ̂ = T(F̂_n). Efron's bootstrap approximates (θ̂ − θ) by drawing B random samples x^*(b) of size n with replacement from {x₁, ..., x_n}. The probability that observation x_i is omitted from all n draws of a single replicate is (1 − 1/n)ⁿ → e⁻¹ = exp(−1) ≈ 0.3679 as n → ∞. Thus, an average bootstrap resample contains 1 − e⁻¹ ≈ 63.21% of the unique original observations, leaving ~36.79% as "out-of-bag" points.

Bootstrap Standard Error, Bias Estimation, and Confidence Intervals

From B bootstrap replicates θ̂^*(b) = s(x^*(b)) (B = 1,000–10,000), the bootstrap standard error (SE_boot) and bias (Bias_boot = θ̂^*(·) − θ̂) are the sample standard deviation and mean shift of the resampled estimates:

SE_boot = √[ (1 / (B − 1)) ∑_b=1^B ( θ̂^*(b) − θ̂^*(·) )² ]

Confidence intervals at 100(1 − α)% are built via four methods: (1) Percentile Intervals, using the empirical α/2 and 1 − α/2 quantiles (O(n^−1/2) coverage error); (2) Basic Pivotal Intervals [ 2*θ̂* − θ̂^*(1−α/2), 2*θ̂* − θ̂^*(α/2) ]; (3) Studentized (Bootstrap-t) Intervals; and (4) Efron's (1987) Bias-Corrected and Accelerated (BC_a) Interval, adjusting quantiles via median bias (ẑ₀) and jackknife skewness (â) for second-order accuracy (O(n⁻¹)).

Felsenstein's Multinomial Alignment Resampling (1985)

In 1985, evolutionary geneticist Joseph Felsenstein adapted Efron's nonparametric bootstrap to evaluate confidence in inferred phylogenetic trees. Given a multiple sequence alignment A of M taxa across L homologous nucleotide or amino acid columns (sites), the evolutionary tree τ is estimated via Maximum Parsimony, Neighbor-Joining, or Maximum Likelihood (ML). Under Felsenstein's phylogenetic bootstrap, the L alignment columns are treated as independent samples of evolutionary character history. To generate a single bootstrap replicate alignment A^*(b) of identical dimensions (M × L), the algorithm draws L columns with replacement from A, re-estimates the phylogenetic tree τ̂^*(b), and repeats this procedure B = 100 to 1,000 times. The bootstrap support proportion (BP) plotted on an internal branch is the percentage of bootstrap trees in which that clade bipartition is recovered.

Hillis–Bull Conservative Interpretation and Ultrafast Bootstrap (UFBoot2)

Because phylogenetic tree space has curved boundaries around internal four-taxon quartets, the statistical meaning of a phylogenetic bootstrap proportion (BP) differs from a Bayesian posterior probability (PP). In simulation studies, David M. Hillis and James J. Bull (1993) demonstrated that under symmetric equal-rate evolution, Felsenstein's bootstrap is conservative as a direct estimator of clade probability: clades receiving BP ≥ 70% correspond to a true clade recovery probability of ≥ 95% in balanced four-taxon simulations, whereas Bayesian MCMC posterior probabilities yield higher numerical values (PP ≥ 0.95 corresponding roughly to standard BP ≥ 70–80%). To accelerate ML bootstrapping on genome-scale alignments, Bui Quang Minh and colleagues (2013, 2018) developed the Ultrafast Bootstrap (UFBoot2) in IQ-TREE, using Resampling Estimated Log-Likelihoods (RELL) so that support values behave as unbiased probabilities requiring UFBoot ≥ 95%.

Boundary Statistics and Heavy-Tailed Distributions

Although the nonparametric bootstrap is consistent across smooth functionals (proven via Edgeworth expansions by Peter Hall and Kesar Singh), it fails when T(F) lies on a parameter boundary. If x₁, ..., x_n come from Uniform(0, θ) and θ is estimated by the sample maximum x_(n), every resample draws from {x₁, ..., x_n}, so x_(n)^* never exceeds x_(n) and equals x_(n) with probability 1 − (1 − 1/n)ⁿ ≈ 0.632, failing to converge to the Weibull boundary distribution. Similarly, under heavy-tailed Pareto or Cauchy distributions with infinite variance (α < 2), the n-out-of-n bootstrap mean diverges, requiring the m-out-of-n bootstrap (m/n → 0) or subsampling.

Dependent Time Series and Multi-Locus Phylogenomics

When observations exhibit temporal or spatial dependence, resampling individual data points x_t destroys serial autocorrelation ρ(k) and underestimates standard errors. For stationary time series, Hans R. Künsch's (1989) moving-block bootstrap and Dimitris N. Politis and Joseph P. Romano's stationary bootstrap preserve short-range correlation by resampling contiguous overlapping blocks of length l (~n^1/3). Analogously, in multi-locus phylogenomics where individual gene trees conflict due to incomplete lineage sorting, resampling concatenated alignment columns treats all sites as independent and inflates clade support toward 100%, requiring a two-stage gene-and-site bootstrap that resamples loci first and sites within loci second.

Why does each bootstrap sample contain approximately 63.2% of the original data points?

When drawing n observations with replacement from a dataset of size n, any single observation has a 1/n chance of being chosen and a (1 − 1/n) chance of being missed on each draw. Across n independent draws, the probability that a specific observation is never chosen is (1 − 1/n)ⁿ. By calculus, as n grows large, (1 − 1/n)ⁿ converges to Euler's constant inverse e⁻¹ ≈ 0.3679 (36.8% omitted), meaning 1 − e⁻¹ ≈ 0.6321 (63.2%) of unique original observations are included.

What is the difference between bootstrapping, jackknifing, and permutation testing?

Bootstrapping draws B random samples of size n with replacement to estimate standard errors and confidence intervals around an observed statistic θ̂. The jackknife (Quenouille 1949; Tukey 1958) deterministically leaves out one observation at a time (n subsamples of size n − 1 without replacement) as a linear Taylor approximation to the bootstrap. In contrast, a permutation test shuffles group labels without replacement across pooled treatments to simulate the null hypothesis (H₀: no difference between groups) and compute a two-sample p-value.

Why is an Ultrafast Bootstrap (UFBoot) threshold of 95% required instead of 70%?

Standard nonparametric phylogenetic bootstrapping (Felsenstein 1985) exhibits a downward conservative bias because optimizing a full tree from scratch on resampled columns frequently splits support across near-neighbor topologies, so a standard BP of 70–80% already corresponds to ~95% probability that a clade is real. In contrast, IQ-TREE's Ultrafast Bootstrap (UFBoot2) uses RELL log-likelihood resampling across all candidate topologies discovered during tree search, correcting this conservative bias so that UFBoot values behave as unbiased probabilities requiring a ≥95% threshold.

1. Efron, B. (1979). "Bootstrap methods: Another look at the jackknife." The Annals of Statistics, 7(1), 1–26. https://doi.org/10.1214/aos/1176344552
2. Felsenstein, J. (1985). "Confidence limits on phylogenies: An approach using the bootstrap." Evolution, 39(4), 783–791. https://doi.org/10.1111/j.1558-5646.1985.tb00420.x
3. Efron, B. (1987). "Better bootstrap confidence intervals." Journal of the American Statistical Association, 82(397), 171–185. https://doi.org/10.1080/01621459.1987.10478410
4. Hoang, D. T., Chernomor, O., von Haeseler, A., Minh, B. Q., & Vinh, L. S. (2018). "UFBoot2: Improving the ultrafast bootstrap approximation." Molecular Biology and Evolution, 35(2), 518–522. https://doi.org/10.1093/molbev/msx281