The Bootstrap and Resampling

You have one sample of 5,000 sessions and you need a confidence interval on the 95^th percentile of latency. There is no textbook formula for the standard error of a sample quantile that you would trust on a skewed, multimodal distribution. Efron's answer in 1979 was to stop looking for a formula: resample the data with replacement 10,000 times, compute the statistic on each resample, and read the interval off the resulting spread (Efron, 1979, Bootstrap Methods: Another Look at the Jackknife, Annals of Statistics 7(1)).

The idea rests on one substitution. The sampling distribution of a statistic depends on the unknown population \(F\). The bootstrap replaces \(F\) with the empirical distribution \(\hat{F}_n\), which puts mass \(1/n\) on each observed point, and then computes exactly, by simulation, what the theory would have computed analytically.

The algorithm and what it is approximating

For \(B\) replicates, draw \(n\) observations with replacement from the original \(n\), compute the statistic \(\hat{\theta}^{*b}\), and collect them. The spread of \(\{\hat{\theta}^{*1}, \dots, \hat{\theta}^{*B}\}\) estimates the spread of \(\hat{\theta}\) under repeated sampling from the population.

Two sources of error stack. The statistical error is that \(\hat{F}_n \neq F\), and it shrinks with \(n\); no amount of resampling fixes it. The Monte Carlo error is that \(B\) is finite, and it shrinks with \(B\); it is free to fix by resampling more. A common confusion is treating a large \(B\) as if it compensated for a small \(n\). It does not. With \(n = 12\) observations, the bootstrap has twelve distinct values to work with no matter how many times you resample them.

For interval endpoints you want \(B\) in the thousands, because the tails are estimated from the extreme order statistics of the replicate distribution. \(B = 200\) is enough for a standard error and badly insufficient for a 99% interval.

Which interval to use

The percentile interval takes the empirical 2.5^th and 97.5^th quantiles of the replicates. It is correct when the statistic's sampling distribution is symmetric and its spread does not depend on the parameter; it is biased otherwise.

The basic (or reverse percentile) interval reflects the replicates around the observed estimate, \([2\hat{\theta} - \hat{\theta}^*_{(0.975)},\; 2\hat{\theta} - \hat{\theta}^*_{(0.025)}]\), which corrects for bias in the location but can produce impossible endpoints (a negative variance, a probability above 1).

BCa (bias-corrected and accelerated) adjusts the quantile levels using an estimated bias term and an acceleration term derived from the jackknife. It is second-order accurate where the percentile method is first-order, meaning its coverage error shrinks like \(1/n\) rather than \(1/\sqrt{n}\). It costs an extra \(n\) statistic evaluations and it is the default worth reaching for when coverage actually matters.

There is also the studentised bootstrap, which bootstraps the t-statistic rather than the estimate. It has the best asymptotic properties and requires a variance estimate inside each replicate, so it is often a nested bootstrap and correspondingly expensive.

Resampling the right unit

The bootstrap assumes the resampled units are exchangeable. When they are not, you must resample at the level where independence holds.

For clustered data (many events per user), resample users and take all of each sampled user's events. This is the cluster bootstrap, and it is the difference between a correct interval and one that is three times too narrow. For time series, resampling individual points destroys the autocorrelation that defines the problem; the block bootstrap resamples contiguous blocks of length \(\ell\), which preserves dependence within a block at the cost of breaking it at block boundaries. Choosing \(\ell\) is a real bias-variance decision and there is no default that is right across problems.

When it breaks

Statistics that depend on the extremes. The maximum of a sample is the canonical failure. A bootstrap resample can never exceed the observed maximum, so the bootstrap distribution of the max is degenerate on one side and the interval is nonsense. Anything driven by the boundary of the support inherits this.

Very small samples. With \(n\) under about 20, \(\hat{F}_n\) is a poor stand-in for \(F\) and coverage degrades in a way no interval variant repairs. The number of distinct resamples is finite and the granularity of the replicate distribution becomes visible.

Heavy tails without moments. If the population has infinite variance, the sample mean has no limiting normal distribution and the bootstrap for the mean is inconsistent. This is not exotic: revenue-per-user distributions are frequently heavy enough that this matters at realistic sample sizes, which is why trimmed or winsorised metrics are standard in experimentation.

Non-smooth functionals. Statistics that are not smooth functions of the empirical distribution, including some model-selection outputs and certain constrained estimators, break the theoretical guarantee. The bootstrap runs happily and returns a number, which is the dangerous part.