The Plug-In Principle and Why the Bootstrap Works

Why resampling one sample says something true about samples not drawn. Parameters as functions of a distribution and the empirical distribution as their plug-in estimate (its maximum likelihood property proved); the Glivenko–Cantelli theorem proved from the strong law; when plug-in estimates are consistent, and why the mean is a warning case; the bootstrap as the plug-in principle applied to a sampling distribution, with the exact bootstrap mean and variance; bootstrap consistency for the mean, the studentized mean and smooth functions of a mean, proved under a finite variance alone; and the sample maximum, where the bootstrap provably fails. Measured on C-reactive protein in 5,146 adults, a population with skewness 7.9. Worked problems on an exact bootstrap distribution, the bootstrap maximum, the plug-in AUC and the sample size for a distribution-free band.

Thirty adults drawn at random from the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 have a mean C-reactive protein (CRP) of 5.68 mg/L, with a standard deviation of 8.72 and one value, 44.63, more than twice the next largest. Resampling those thirty numbers with replacement and recomputing the mean many times gives a standard error of about 1.57 mg/L, which turns out to be close to the true standard error of a mean of thirty, 1.50. Nothing in the resampling looked at any adult outside the thirty. Why should shuffling one sample say anything true about samples that were never drawn?

The answer is the plug-in principle: write the quantity wanted as a function of the unknown distribution $F$, and evaluate that function at the empirical distribution $\hat F_n$, which puts probability $1/n$ on each observation. The bootstrap is this principle applied to one particular quantity, the sampling distribution of an estimate. It works when two things hold: $\hat F_n$ is close to $F$, and the quantity depends on the distribution smoothly enough that closeness carries over.

First we write parameters as functions of a distribution and show that the empirical distribution is the maximum likelihood estimate of $F$. Then we prove the Glivenko–Cantelli theorem, which says that $\hat F_n$ converges to $F$ uniformly, and ask which plug-in estimates inherit that convergence. Next we describe the bootstrap as a plug-in estimate and prove that it is consistent for the mean, the studentized mean and smooth functions of a mean, needing only a finite variance. Finally we measure how well it works on CRP, prove that it fails for the sample maximum, and work four problems. The article assumes The Laws of Large Numbers and Convergence in Distribution and the Proof of the Central Limit Theorem. The library's The Bootstrap Method is the practical companion: it shows the method at work on regression and prediction error, and this article supplies the theory beneath it.

This article is the first of the Resampling Methods unit. Later articles build on the consistency theorems proved here: Bootstrap Confidence Intervals: Percentile, Basic, Studentized and BCa turns them into intervals, and the unit's other articles link here for the statement that the bootstrap is consistent for the mean.

The running example: thirty adults from a skewed population

The unit's population is the 5,146 adults of NHANES 2017 to 2018 with a high-sensitivity CRP measurement (National Center for Health Statistics, 2020). The Central Limit Theorem introduced it as a population about as far from normal as a medical measurement gets. Its mean is $\mu = 4.17$ mg/L, its standard deviation (divisor $N$) $\sigma = 8.20$, its median 1.94 and its largest value 182.82; its skewness is 7.89. The unit treats these adults as a finite population with distribution function $F$ and draws samples from it with replacement, so that the draws are independent and identically distributed (i.i.d.) with distribution exactly $F$. That is a device for checking methods against a known truth. NHANES is a complex survey, and estimates for the United States population would need its sampling weights, which are not used here.

The running sample is $n = 30$ draws made with NumPy's default_rng(20261118). Sorted, the thirty values are

0.32, 0.33, 0.58, 0.87, 0.89, 0.92, 0.94, 1.02, 1.13, 1.14, 1.32, 1.32, 1.35, 1.56, 1.58, 2.51, 2.85, 3.55, 4.48, 5.51, 5.74, 6.53, 6.62, 6.90, 9.26, 11.25, 12.95, 13.28, 19.01, 44.63.

Their mean is $\bar x = 5.68$, their sample standard deviation $s = 8.72$ (divisor $n - 1$), and their median 2.045, the average of the fifteenth and sixteenth values. The largest value is 44.63. The plug-in skewness of the sample is 3.22, far below the population's 7.89. Only 33 of the 5,146 adults have a value above 50 mg/L, yet they hold 11.9% of the population's total CRP, and a sample of thirty includes at least one of them with probability 0.176. Those rare values are what make the population's tail so long, and most samples of thirty, this one included, never see them. The sample has the population's character, piled near zero with a long right tail, but it is only thirty numbers.

Parameters as functions of a distribution

A statistical functional is a rule $T$ that assigns a number $T(G)$ to each distribution $G$ in some class. The parameters of elementary statistics are all of this kind:

Parameter $T(G)$ Plug-in estimate $T(\hat F_n)$
mean $\int x\,dG(x)$ $\bar x$
variance $\int (x - \mu_G)^2\,dG(x)$ $\hat\sigma_n^2 = \frac1n\sum (x_i - \bar x)^2$
$u$-quantile $Q_G(u) = \inf\{x : G(x) \ge u\}$ the $\lceil nu\rceil$-th smallest value
$P(X > Y) + \frac12 P(X = Y)$ for $X \sim G_1$, $Y \sim G_0$ independent the Mann–Whitney count of pairs

The integral $\int g(x)\,dG(x)$ stands for $E[g(X)]$ when $X$ has distribution $G$, whether $G$ has a density, a mass function or neither (Expectation, Variance and Covariance defines the expected value for every random variable).

The empirical distribution function of the observations $x_1, \ldots, x_n$ is

$$\hat F_n(x) = \frac{1}{n}\sum_{i=1}^{n} \mathbf{1}\{x_i \le x\},$$

the share of the sample at or below $x$. It is the distribution function of a random variable that takes each observed value with probability $1/n$ (a value observed twice gets $2/n$). Tables and Graphs for Data draws it for the 5,247 systolic pressures of the course. The plug-in estimate of $\theta = T(F)$ is $\hat\theta = T(\hat F_n)$: the parameter computed as if the sample were the population.

Two remarks on the table. The plug-in variance has divisor $n$, not $n - 1$, so it is biased downward by the factor $(n-1)/n$, as Maximum Likelihood Estimation shows for the normal; the plug-in principle does not promise unbiased estimates. And the plug-in median is the smallest value with at least half the sample at or below it, the fifteenth of thirty values (1.58 here), not the average of the two middle values that the course and NumPy report. The two differ by at most the gap between neighboring order statistics. The theorems below are stated for the plug-in median, and the quantile example below extends to the average: when $F$ rises immediately on both sides of the median $q$, so that $F(q - \varepsilon) < \frac12 < F(q + \varepsilon)$ for every $\varepsilon > 0$, the same argument with $\delta = \min\big(\frac12 - F(q - \varepsilon),\ F(q + \varepsilon) - \frac12\big) - \frac1n$ (positive for large $n$) puts, for even $n$, both middle order statistics, the plug-in quantiles at levels $\frac12$ and $\frac12 + \frac1n$, within $\varepsilon$ of $q$, so their average converges to $q$ as well; for odd $n$ the average is the plug-in median itself.

Why $\hat F_n$ and not some smoother estimate of $F$? Without a model for $F$, it is the distribution that makes the observed sample most probable.

Theorem 1 (the empirical distribution is the nonparametric maximum likelihood estimate). Let $v_1, \ldots, v_k$ be the distinct values among $x_1, \ldots, x_n$, with counts $c_1, \ldots, c_k$. Among all distributions $G$ on the real line, the likelihood $L(G) = \prod_{i=1}^n G(\{x_i\})$, where $G(\{x\})$ is the probability $G$ gives to the single point $x$, is largest for $G = \hat F_n$, and only there.

Here is the idea: the likelihood only rewards probability placed on the observed points, and the best way to share a total of at most 1 among them is in proportion to their counts.

Proof. Write $p_j = G(\{v_j\})$. Then $L(G) = \prod_j p_j^{c_j}$, and $p_1 + \cdots + p_k \le 1$ because the points are distinct. If some $p_j = 0$ the likelihood is 0, which $\hat F_n$ beats, since it gives $L = \prod_j (c_j/n)^{c_j} > 0$. Otherwise take logarithms and divide by $n$: $\frac1n \ln L(G) = \sum_j \frac{c_j}{n}\ln p_j$. Gibbs' inequality in the form that allows the $p_j$ to sum to at most 1, proved in Cross-Entropy and Kullback–Leibler Divergence (section "Gibbs' inequality"), says $\sum_j \frac{c_j}{n}\ln p_j \le \sum_j \frac{c_j}{n}\ln\frac{c_j}{n}$, with equality only when $p_j = c_j/n$ for every $j$. Those probabilities sum to 1, so equality forces $G$ to put all its probability on the observed values in the observed proportions, which is $\hat F_n$. $\square$

A distribution with a density gives every single point probability 0 and has likelihood 0 in this sense; the theorem compares distributions by the probability they give the observed values themselves. Efron and Hastie (2016, Section 10.2) state the same property of $\hat F_n$.

The empirical distribution converges: the Glivenko–Cantelli theorem

For a fixed $x$, $\hat F_n(x)$ is the mean of the i.i.d. indicators $\mathbf{1}\{X_i \le x\}$, whose mean is $F(x)$, so $\hat F_n(x) \to F(x)$ with probability 1 by the strong law. The plug-in principle needs more: one sample must make $\hat F_n$ close to $F$ at every $x$ at once. Measure closeness by the Kolmogorov distance

$$d_K(G, H) = \sup_x \lvert G(x) - H(x)\rvert,$$

the largest vertical gap between two distribution functions.

Theorem 2 (Glivenko–Cantelli). If $X_1, X_2, \ldots$ are i.i.d. with distribution function $F$, then $d_K(\hat F_n, F) \to 0$ with probability 1.

Here is the idea in two sentences. Pointwise convergence at finitely many well-chosen points is enough, because between two neighboring points both functions are nondecreasing and $F$ climbs by at most a small amount. Choosing the points at the quantiles of $F$ handles the jumps of $F$ as well, provided convergence is also checked just to the left of each point.

Proof. Fix a whole number $k \ge 2$ and let $q_j = Q(j/k)$ for $j = 1, \ldots, k-1$, where $Q$ is the quantile function of $F$; set $q_0 = -\infty$ and $q_k = +\infty$, with $F(-\infty) = \hat F_n(-\infty) = 0$ and $F(+\infty) = \hat F_n(+\infty) = 1$. Write $F(x-) = P(X < x)$ for the limit from the left.

Step 1: what $F$ does between the points. By the inequality $Q(u) \le x \iff u \le F(x)$ (Random Variables and Distribution Functions, Theorem 2), two facts hold for $1 \le j \le k - 1$. Taking $x = q_j$ gives $F(q_j) \ge j/k$. And every $y < q_j$ has $F(y) < j/k$, so $F(q_j-) \le j/k$. The same holds trivially at $j = 0$ and $j = k$. Hence for $1 \le j \le k$,

$$F(q_j-) - F(q_{j-1}) \le \frac{j}{k} - \frac{j-1}{k} = \frac{1}{k}.$$

Step 2: convergence at the finitely many points. The indicators $\mathbf{1}\{X_i \le q_j\}$ are i.i.d. with mean $F(q_j)$, and the indicators $\mathbf{1}\{X_i < q_j\}$ are i.i.d. with mean $F(q_j-)$. Indicators are bounded, so they have a finite fourth moment, and the strong law proved in The Laws of Large Numbers (section "The strong law under a finite fourth moment") gives $\hat F_n(q_j) \to F(q_j)$ and $\hat F_n(q_j-) \to F(q_j-)$ with probability 1, where $\hat F_n(q_j-)$ is the share of the sample strictly below $q_j$. There are finitely many of these events, each of probability 1, so they hold together with probability 1. On that event,

$$\varepsilon_n = \max_{0 \le j \le k}\max\big(\lvert\hat F_n(q_j) - F(q_j)\rvert,\ \lvert\hat F_n(q_j-) - F(q_j-)\rvert\big) \to 0.$$

Step 3: between the points. Let $q_{j-1} < x < q_j$. Both functions are nondecreasing, so

$$\hat F_n(x) \le \hat F_n(q_j-) \le F(q_j-) + \varepsilon_n \le F(q_{j-1}) + \tfrac1k + \varepsilon_n \le F(x) + \tfrac1k + \varepsilon_n,$$

$$\hat F_n(x) \ge \hat F_n(q_{j-1}) \ge F(q_{j-1}) - \varepsilon_n \ge F(q_j-) - \tfrac1k - \varepsilon_n \ge F(x) - \tfrac1k - \varepsilon_n.$$

At the points $q_j$ themselves the gap is at most $\varepsilon_n$. Every real $x$ is either one of the points or between two neighbors, so $d_K(\hat F_n, F) \le \frac1k + \varepsilon_n$, and $\limsup_n d_K(\hat F_n, F) \le \frac1k$ with probability 1.

Step 4: all $k$ at once. The event "$\limsup_n d_K(\hat F_n, F) \le 1/k$" has probability 1 for each $k = 2, 3, \ldots$; a countable intersection of events of probability 1 has probability 1, and on it the limit superior is 0. $\square$

The proof follows Durrett (2019, Theorem 2.4.9), with the strong law for bounded variables, which this site proves, in place of the general strong law. Nothing is assumed about $F$: it may have jumps, as the CRP population does (its values are recorded to 0.01 mg/L, and twelve adults share the smallest value), and it need not have a mean.

How fast. The theorem gives no rate. A sharp one is the Dvoretzky–Kiefer–Wolfowitz inequality with the constant found by Massart (1990), stated in his abstract for i.i.d. observations with any distribution function $F$, and cited, not proved, here: for every $n$ and every $\lambda > 0$,

$$P\big(\sqrt n\, d_K(\hat F_n, F) > \lambda\big) \le 2e^{-2\lambda^2}.$$

The CRP population has jumps, so it is worth seeing why nothing about $F$ matters: the general case reduces to the uniform one. The probability in the inequality depends only on the joint distribution of $X_1, \ldots, X_n$, so we may take $X_i = Q(U_i)$ with $U_1, U_2, \ldots$ i.i.d. uniform on $(0, 1)$ and $Q$ the quantile function of $F$; the $X_i$ then have distribution function $F$ (Random Variables and Distribution Functions, Theorem 3, the inverse transform). By Theorem 2 there, $Q(U_i) \le x$ exactly when $U_i \le F(x)$, so $\hat F_n(x) = \hat U_n(F(x))$, where $\hat U_n$ is the empirical distribution function of the $U_i$. Hence $d_K(\hat F_n, F) = \sup_x\lvert\hat U_n(F(x)) - F(x)\rvert \le \sup_u\lvert\hat U_n(u) - u\rvert$, so the inequality for the uniform distribution gives it for every $F$.

Setting the right side to 0.05 gives a band of half-width $\varepsilon_n = \sqrt{\ln(40)/(2n)}$ around $\hat F_n$ that contains all of $F$ with probability at least 95%, whatever $F$ is. The script drew 30 independent samples of each size from the CRP population (NumPy seeds $1{,}000n$ to $1{,}000n + 29$ for size $n$, so that no sample is part of another) and computed $d_K(\hat F_n, F)$ exactly:

$n$ median $d_K(\hat F_n, F)$ interquartile range $\sqrt n \times$ median 95% band $\varepsilon_n$
30 0.138 0.115 to 0.182 0.76 0.248
100 0.083 0.075 to 0.097 0.83 0.136
400 0.039 0.036 to 0.050 0.78 0.068
1,600 0.018 0.015 to 0.027 0.74 0.034
6,400 0.010 0.008 to 0.012 0.80 0.017

In this experiment the distance fell in proportion to $1/\sqrt n$: the middle column times $\sqrt n$ stays between 0.74 and 0.83. Twelve of the 150 samples landed outside their 95% band, against an expected number of at most 7.5. A binomial count with 150 trials and probability 0.05 reaches 12 or more with probability 0.074, so the count is higher than expected but not strong evidence against the inequality, which is a theorem. The 0.074 is itself an upper bound: for this population each sample's chance of leaving its band is at most 0.05, and may be less. At $n = 30$ the empirical distribution of the running sample is, typically, 0.14 away from the truth somewhere. That is close in the sense of the theorem and still a long way from the population, which is why the bootstrap's accuracy at small $n$ has to be measured rather than assumed.

Which plug-in estimates converge?

If $\hat F_n$ is close to $F$, is $T(\hat F_n)$ close to $T(F)$? It is when $T$ does not change much under small changes of its argument. Call $T$ continuous at $F$ (in the Kolmogorov distance) if for every $\varepsilon > 0$ there is $\delta > 0$ such that $d_K(G, F) < \delta$ implies $\lvert T(G) - T(F)\rvert < \varepsilon$.

Theorem 3 (consistency of plug-in estimates). If $T$ is continuous at $F$, then $T(\hat F_n) \to T(F)$ with probability 1.

Proof. On the event of Theorem 2, which has probability 1, $d_K(\hat F_n, F) < \delta$ for all large $n$, so $\lvert T(\hat F_n) - T(F)\rvert < \varepsilon$ for all large $n$. As $\varepsilon$ was arbitrary, $T(\hat F_n) \to T(F)$. $\square$

Example (quantiles). Let $q = Q_F(u)$ for some $0 < u < 1$, and suppose $F(q + \varepsilon) > u$ for every $\varepsilon > 0$, that is, $F$ rises above $u$ immediately to the right of $q$. Then the quantile functional is continuous at $F$, and the plug-in quantile converges to $q$. Fix $\varepsilon > 0$. Since $q$ is the smallest $x$ with $F(x) \ge u$, $F(q - \varepsilon) < u$. Let $\delta = \min\big(u - F(q - \varepsilon),\ F(q + \varepsilon) - u\big) > 0$. If $d_K(G, F) < \delta$, then $G(q - \varepsilon) < F(q - \varepsilon) + \delta \le u$, so no $x \le q - \varepsilon$ has $G(x) \ge u$ and $Q_G(u) > q - \varepsilon$; and $G(q + \varepsilon) > F(q + \varepsilon) - \delta \ge u$, so $Q_G(u) \le q + \varepsilon$. The condition matters. If $F$ is flat at height exactly $u$ on an interval to the right of $q$, the sample quantile can jump between the two ends of the flat stretch forever.

Example (the mean is not continuous, and why that matters). A common misreading is that every plug-in estimate is consistent because $\hat F_n$ converges to $F$. The mean shows why that reasoning fails. Let $G_\delta$ be the mixture that draws from $F$ with probability $1 - \delta$ and returns the single value $1/\delta^2$ with probability $\delta$, so that $G_\delta(x) = (1 - \delta)F(x) + \delta\,\mathbf{1}\{x \ge 1/\delta^2\}$. Then $G_\delta(x) - F(x) = \delta\big(\mathbf{1}\{x \ge 1/\delta^2\} - F(x)\big)$ lies between $-\delta$ and $\delta$, so $d_K(G_\delta, F) \le \delta$, while the mean of $G_\delta$ is $(1 - \delta)\mu + 1/\delta$, which grows without bound as $\delta \to 0$. Arbitrarily small Kolmogorov distance allows an arbitrarily large change of the mean, because the distance does not see where far-out probability sits. The sample mean is still consistent, but the reason is the law of large numbers, which uses the finite mean of $F$, not Theorem 3. The same blind spot is why a long right tail, which the CRP sample of thirty barely samples, is the bootstrap's weak point for means. The theorems below put the needed moment condition in explicitly.

The bootstrap is the plug-in principle applied to a sampling distribution

Efron (1979) posed the problem in this form: given a random sample $\mathbf X = (X_1, \ldots, X_n)$ from an unknown $F$, estimate the sampling distribution of a specified random variable $R(\mathbf X, F)$ from the observed data. Such an $R$ is called a root. Examples are $\sqrt n(\bar X_n - \mu)$, the studentized mean $\sqrt n(\bar X_n - \mu)/s_n$, and $\hat\theta - \theta$ for any plug-in estimate. The root's distribution function

$$G_n(x; F) = P_F\big(R(\mathbf X, F) \le x\big)$$

is itself a functional of $F$, and the bootstrap estimates it by plugging in:

$$\hat G_n(x) = G_n(x; \hat F_n) = P_*\big(R(\mathbf X^*, \hat F_n) \le x\big).$$

Here $\mathbf X^* = (X_1^*, \ldots, X_n^*)$ is a bootstrap sample, $n$ i.i.d. draws from $\hat F_n$, that is, $n$ draws with replacement from the observed values. The subscript in $P_*$, $E_*$ and $\operatorname{Var}_*$ means probability, expectation and variance under resampling with the data held fixed. In the bootstrap world $\hat F_n$ plays the part of $F$ and $\hat\theta = T(\hat F_n)$ the part of $\theta$, so the bootstrap version of $\hat\theta - \theta$ is $\hat\theta^* - \hat\theta$, where $\hat\theta^* = T(\hat F_n^*)$ is computed from the bootstrap sample. Efron and Hastie (2016, eq. 10.20) write the bootstrap standard error the same way, as the plug-in estimate $\operatorname{Sd}(\hat F)$ of the standard deviation $\operatorname{Sd}(F)$ of $\hat\theta$.

Two approximations, kept apart. $\hat G_n$ is an exact function of the data. It can rarely be computed exactly, because a bootstrap sample of $n$ values is one of $n^n$ equally likely ordered sequences. As unordered samples, it is one of

$$\binom{2n - 1}{n}$$

distinct multisets, by the count of ways to put $n$ indistinguishable draws into $n$ labeled boxes (write the draws as $n$ stars and the boxes' boundaries as $n - 1$ bars, and choose which of the $2n - 1$ positions are stars). For $n = 30$ that is $5.91 \times 10^{16}$. So in practice $\hat G_n$ is estimated by Monte Carlo: draw $B$ bootstrap samples, compute the root on each, and use the empirical distribution of the $B$ values, $\hat G_B$. The error of $\hat G_n$ as an estimate of $G_n(\cdot\,; F)$ is the statistical error, fixed by $n$ and the data. The error of $\hat G_B$ as an estimate of $\hat G_n$ is Monte Carlo error, which shrinks as $B$ grows, with $\sup_x \lvert\hat G_B(x) - \hat G_n(x)\rvert \to 0$ by Theorem 2 applied to the $B$ resampled values. The Bootstrap Method measures how large $B$ must be in practice. The theorems of this article concern the statistical error, with $\hat G_n$ computed exactly.

For the mean, the ideal bootstrap's center and spread can be computed exactly.

Theorem 4 (the bootstrap mean). Given data $x_1, \ldots, x_n$ with mean $\bar x$ and plug-in variance $\hat\sigma_n^2 = \frac1n\sum_i (x_i - \bar x)^2$, the mean $\bar X^*$ of a bootstrap sample has

$$E_*[\bar X^*] = \bar x, \qquad \operatorname{Var}_*(\bar X^*) = \frac{\hat\sigma_n^2}{n}.$$

Proof. Each $X_i^*$ takes each $x_j$ with probability $1/n$, so $E_*[X_i^*] = \bar x$ and $\operatorname{Var}_*(X_i^*) = \frac1n\sum_j (x_j - \bar x)^2 = \hat\sigma_n^2$. The $X_i^*$ are independent under resampling, so the mean of $n$ of them has expectation $\bar x$ and variance $\hat\sigma_n^2/n$ (Expectation, Variance and Covariance, variance of a sum of independent variables). $\square$

So the ideal bootstrap standard error of a mean is $\hat\sigma_n/\sqrt n$, the textbook $s/\sqrt n$ multiplied by $\sqrt{(n-1)/n}$. For the running sample it is $8.572/\sqrt{30} = 1.565$, against $s/\sqrt{30} = 1.592$ and the true $\sigma/\sqrt{30} = 1.498$; the factor $\sqrt{29/30} = 0.9832$ is the plug-in principle's divisor $n$ showing through. Two thousand resamples (seed 1) gave 1.503, a Monte Carlo estimate of 1.565 that happens to be low: in 200 further replications of 2,000 resamples each (seed 777), the estimates had mean 1.562 and standard deviation 0.03, and 2% of them were at or below 1.503. The bootstrap needs no formula for the mean. Theorem 4 matters because it shows what the bootstrap does when a formula exists: it reproduces the formula with $F$ replaced by $\hat F_n$.

Why it works for the mean

The question of the opening has a precise form. Write

$$K_n(x) = P\big(\sqrt n(\bar X_n - \mu) \le x\big), \qquad \hat H_n(x) = P_*\big(\sqrt n(\bar X^* - \bar X_n) \le x\big)$$

for the true distribution function of the root and its bootstrap estimate. Here is the plan in plain words. The central limit theorem says that $K_n$ approaches a normal distribution with mean 0 and standard deviation $\sigma$. The bootstrap root is also a standardized sum of i.i.d. terms, drawn from $\hat F_n$ instead of $F$, so the same proof should show that $\hat H_n$ approaches a normal with standard deviation $\hat\sigma_n$, which itself approaches $\sigma$. The one new difficulty is that the distribution being sampled, $\hat F_n$, changes with $n$, and the proof of the central limit theorem used a single fixed distribution. The fix is to control the largest observation.

Lemma 1 (the largest observation is small compared with $\sqrt n$). If $X_1, X_2, \ldots$ are i.i.d. with $E[X_1^2] < \infty$, then $\max_{i \le n}\lvert X_i\rvert/\sqrt n \to 0$ with probability 1.

Proof. Fix $\varepsilon > 0$ and let $W = X_1^2/\varepsilon^2$, a nonnegative variable with finite mean. For $i - 1 \le t \le i$, $P(W > i) \le P(W > t)$, so summing over $i \ge 1$,

$$\sum_{i=1}^\infty P(X_i^2 > \varepsilon^2 i) = \sum_{i=1}^\infty P(W > i) \le \int_0^\infty P(W > t)\,dt = E[W] < \infty,$$

using that the $X_i$ share the distribution of $X_1$, and the tail formula for the expected value of a nonnegative variable (Expectation, Variance and Covariance, which defines $E$ that way). By the first Borel–Cantelli lemma (The Laws of Large Numbers), with probability 1 only finitely many of the events $\{\lvert X_i\rvert > \varepsilon\sqrt i\}$ occur: there is an index $I$, depending on the outcome, with $\lvert X_i\rvert \le \varepsilon\sqrt i$ for every $i > I$. For $n > I$,

$$\frac{\max_{i \le n}\lvert X_i\rvert}{\sqrt n} \le \frac{\max_{i \le I}\lvert X_i\rvert}{\sqrt n} + \max_{I < i \le n}\frac{\varepsilon\sqrt i}{\sqrt n} \le \frac{\max_{i \le I}\lvert X_i\rvert}{\sqrt n} + \varepsilon,$$

and the first term tends to 0. So $\limsup_n \max_{i \le n}\lvert X_i\rvert/\sqrt n \le \varepsilon$ with probability 1. Taking $\varepsilon = 1, \frac12, \frac13, \ldots$ and intersecting the countably many events of probability 1 gives the limit 0. $\square$

Theorem 5 (bootstrap consistency for the mean). Let $X_1, X_2, \ldots$ be i.i.d. with mean $\mu$ and variance $0 < \sigma^2 < \infty$. Then with probability 1,

$$\sup_x\big\lvert \hat H_n(x) - K_n(x)\big\rvert \to 0.$$

The statement is about almost every infinite sequence of data: for such a sequence, the bootstrap distribution computed from its first $n$ terms approaches the true sampling distribution, uniformly in $x$.

Proof. Step 0: a set of good data sequences. Let $\Omega_0$ be the set of outcomes on which (i) $\bar x_n \to \mu$, (ii) $\frac1n\sum_{i \le n} x_i^2 \to E[X_1^2]$, and (iii) $\max_{i \le n}\lvert x_i\rvert/\sqrt n \to 0$. Parts (i) and (ii) hold with probability 1 by the strong law of large numbers for a finite mean, applied to the $X_i$ and to the $X_i^2$ (cited in The Laws of Large Numbers, section "The strong law in general"; Durrett, 2019, Theorem 2.4.1), and (iii) by Lemma 1, so $P(\Omega_0) = 1$. Fix an outcome in $\Omega_0$. From here on the data are fixed numbers and only the resampling is random. By (i) and (ii), $\hat\sigma_n^2 = \frac1n\sum x_i^2 - \bar x_n^2 \to \sigma^2 > 0$, so $\hat\sigma_n > 0$ for all large $n$.

Step 1: a sum becomes a power. Let $Y_i^* = (X_i^* - \bar x_n)/\hat\sigma_n$. Under resampling the $Y_i^*$ are i.i.d., with $E_*[Y_i^*] = 0$ and $E_*[Y_i^{*2}] = 1$ by Theorem 4's calculation. Let $\varphi_n$ be their common characteristic function. The standardized bootstrap mean $Z_n^* = \sqrt n(\bar X^* - \bar x_n)/\hat\sigma_n = n^{-1/2}\sum_i Y_i^*$ has characteristic function $\varphi_n(t/\sqrt n)^n$, by the rules for independent sums and linear changes.

Step 2: the expansion, with a bound that holds for every $n$. Lemma 5 of the proof of the central limit theorem applies to any variable with mean 0 and variance 1, so to $Y^*$ for each fixed $n$: $\varphi_n(s) = 1 - s^2/2 + r_n(s)$ with $\lvert r_n(s)\rvert \le s^2\,E_*\big[\min\big(\lvert s\rvert\lvert Y^*\rvert^3/6,\ Y^{*2}\big)\big]$. Let $M_n = \max_{i \le n}\lvert x_i - \bar x_n\rvert/\hat\sigma_n$, the largest value $\lvert Y^*\rvert$ can take. Then $\lvert Y^*\rvert^3 \le M_n Y^{*2}$, and

$$\lvert r_n(s)\rvert \le s^2 \cdot \frac{\lvert s\rvert M_n}{6}\,E_*\big[Y^{*2}\big] = \frac{\lvert s\rvert^3 M_n}{6}.$$

In the proof of the central limit theorem the bound on the remainder came from one fixed distribution. Here the distribution changes with $n$, and $M_n$ is what controls it uniformly.

Step 3: the limit. Fix $t$. Step 2 of that proof shows $\lvert a^n - b^n\rvert \le n\lvert a - b\rvert$ for complex numbers of modulus at most 1. With $a = \varphi_n(t/\sqrt n)$ and $b = 1 - t^2/(2n)$, which lies in $[0, 1]$ once $n \ge t^2/2$,

$$\big\lvert \varphi_n(t/\sqrt n)^n - (1 - t^2/(2n))^n\big\rvert \le n\,\big\lvert r_n(t/\sqrt n)\big\rvert \le \frac{\lvert t\rvert^3}{6}\cdot\frac{M_n}{\sqrt n}.$$

Now $M_n/\sqrt n \le (\max_{i \le n}\lvert x_i\rvert + \lvert\bar x_n\rvert)/(\sqrt n\,\hat\sigma_n) \to 0$ by (i), (iii) and $\hat\sigma_n \to \sigma > 0$. And $(1 - t^2/(2n))^n \to e^{-t^2/2}$ (Step 4 of that proof). So the characteristic function of $Z_n^*$ under resampling tends to $e^{-t^2/2}$ for every $t$. By Lévy's continuity theorem (cited in Moment Generating and Characteristic Functions), $Z_n^*$ converges in distribution to the standard normal, and by the theorem on uniform convergence to a continuous limit in the CLT article, $\sup_z\lvert P_*(Z_n^* \le z) - \Phi(z)\rvert \to 0$. The continuity theorem concerns only a sequence of distributions; that each one lives on its own resampling space does not matter.

Step 4: undo the standardization. $\hat H_n(x) = P_*(Z_n^* \le x/\hat\sigma_n)$, so

$$\sup_x\big\lvert \hat H_n(x) - \Phi(x/\sigma)\big\rvert \le \sup_z\big\lvert P_*(Z_n^* \le z) - \Phi(z)\big\rvert + \sup_x\big\lvert \Phi(x/\hat\sigma_n) - \Phi(x/\sigma)\big\rvert.$$

The first term tends to 0 by Step 3. For the second, write $c = \sigma/\hat\sigma_n$ and $y = x/\sigma$, so the term is $\sup_y\lvert\Phi(cy) - \Phi(y)\rvert$. For $\frac12 \le c \le 2$, the mean value theorem gives $\lvert\Phi(cy) - \Phi(y)\rvert = \phi(\xi)\,\lvert c - 1\rvert\,\lvert y\rvert$ for some $\xi$ between $y$ and $cy$, where $\phi$ is the standard normal density; $\lvert\xi\rvert \ge \lvert y\rvert/2$, so this is at most $\lvert c - 1\rvert\,\lvert y\rvert\,\phi(y/2) \le 0.49\,\lvert c - 1\rvert$, because $\lvert y\rvert\phi(y/2) = 2\lvert u\rvert\phi(u)$ with $u = y/2$ is largest at $\lvert u\rvert = 1$, where it equals $2\phi(1) = 0.484$. Since $c \to 1$, the second term tends to 0.

Step 5: compare with the truth. By the Lindeberg–Lévy theorem in the same article, $\sqrt n(\bar X_n - \mu)/\sigma$ converges in distribution to the standard normal, uniformly in $x$, so $\sup_x\lvert K_n(x) - \Phi(x/\sigma)\rvert \to 0$. The triangle inequality finishes the proof. $\square$

Where each hypothesis enters. The finite variance enters three times: it makes $\hat\sigma_n$ converge, it gives Lemma 1, and it makes the true root's limit normal. Independence of the original observations enters through the laws of large numbers and the central limit theorem; independence of the resampled draws is automatic, because resampling is i.i.d. by construction. The bootstrap's own sample size matches the data's: resampling $n$ values to approximate the law of a mean of $n$.

Who proved it first. Bickel and Freedman (1981) and Singh (1981) established the asymptotic validity of the bootstrap for the mean and for $t$ statistics; this article read only their abstracts, which say so. The proof above is a direct adaptation of the characteristic function proof on this site, with Lemma 1 to handle a distribution that changes with $n$.

The studentized mean and smooth functions of a mean

Intervals are built from studentized roots, in which the standard error is estimated from the same sample. In the bootstrap world it is estimated from the bootstrap sample.

Theorem 6 (the studentized mean). Under the hypotheses of Theorem 5, let $s_n$ be the sample standard deviation and $s_n^*$ that of the bootstrap sample. Then with probability 1,

$$\sup_x\Big\lvert P_*\Big(\frac{\sqrt n(\bar X^* - \bar X_n)}{s_n^*} \le x\Big) - P\Big(\frac{\sqrt n(\bar X_n - \mu)}{s_n} \le x\Big)\Big\rvert \to 0.$$

Proof. Fix an outcome in the set $\Omega_0$ of Theorem 5. Write $s_n^{*2} = \frac{n}{n-1}\big(V^* - D^{*2}\big)$ with $V^* = \frac1n\sum_i (X_i^* - \bar x_n)^2$ and $D^* = \bar X^* - \bar x_n$, which is the usual identity for a sum of squared deviations, centered at $\bar x_n$ instead of the bootstrap mean. First, $E_*[V^*] = \hat\sigma_n^2$, and the terms of $V^*$ are i.i.d. under resampling, so

$$\operatorname{Var}_*(V^*) \le \frac{1}{n}E_*\big[(X^* - \bar x_n)^4\big] = \frac{1}{n^2}\sum_i (x_i - \bar x_n)^4 \le \frac{\max_i (x_i - \bar x_n)^2}{n}\,\hat\sigma_n^2 \to 0$$

by (iii). Chebyshev's inequality gives $P_*(\lvert V^* - \hat\sigma_n^2\rvert > \varepsilon) \to 0$ for every $\varepsilon > 0$. Second, $E_*[D^{*2}] = \hat\sigma_n^2/n \to 0$ by Theorem 4, so $P_*(D^{*2} > \varepsilon) \to 0$ by Markov's inequality. With $\hat\sigma_n^2 \to \sigma^2$, these give $s_n^* \to \sigma$ in probability under resampling. Steps 1 to 3 of Theorem 5 showed that $\sqrt n D^*/\hat\sigma_n$ converges in distribution to the standard normal under resampling, so $\sqrt n D^*/s_n^* = (\sqrt n D^*/\hat\sigma_n)(\hat\sigma_n/s_n^*)$ does too, by Slutsky's theorem (the CLT article, section "Slutsky's theorem"), applied for each $n$ on that $n$'s resampling space. The limit is continuous, so the convergence is uniform. On the other side, Corollary 1 of the same article gives the standard normal limit for $\sqrt n(\bar X_n - \mu)/s_n$, uniformly. The triangle inequality finishes the proof. $\square$

Theorem 7 (smooth functions of a mean). Under the hypotheses of Theorem 5, let $g$ be defined on an interval $I$ that contains every possible value of a sample mean (the whole line, or $(0, \infty)$ for positive data, which allows $g = \ln$), and let $g$ have a derivative that is continuous on an open interval around $\mu$, with $g'(\mu) \ne 0$. Then with probability 1,

$$\sup_x\Big\lvert P_*\big(\sqrt n\,(g(\bar X^*) - g(\bar X_n)) \le x\big) - P\big(\sqrt n\,(g(\bar X_n) - g(\mu)) \le x\big)\Big\rvert \to 0.$$

Proof. Fix an outcome in $\Omega_0$, and let $(\mu - c, \mu + c)$ lie inside the interval where $g'$ is continuous. By (i), $\bar x_n$ is in $(\mu - c/2, \mu + c/2)$ for large $n$. By Theorem 4 and Chebyshev's inequality, $P_*(\lvert\bar X^* - \bar x_n\rvert > \eta) \le \hat\sigma_n^2/(n\eta^2) \to 0$ for every $\eta > 0$, so $\bar X^* \to \mu$ in probability under resampling, and the event $A_n$ that $\bar X^*$ lies in $(\mu - c, \mu + c)$ has $P_*(A_n) \to 1$. On $A_n$ the mean value theorem gives $g(\bar X^*) - g(\bar x_n) = g'(\xi^*)(\bar X^* - \bar x_n)$ for some $\xi^*$ between the two means, and $\xi^* \to \mu$ in probability under resampling, so $g'(\xi^*) \to g'(\mu)$ in probability by the continuity of $g'$. Off $A_n$ set $g'(\xi^*) = g'(\mu)$; that changes the root only on an event whose probability tends to 0. Slutsky's theorem and Steps 1 to 4 of Theorem 5 then give a normal limit with mean 0 and standard deviation $\lvert g'(\mu)\rvert\sigma$ under resampling. The true root has the same limit by the same argument, which needs $g$ only near $\mu$: Chebyshev's inequality puts $\bar X_n$ in $(\mu - c, \mu + c)$ with probability tending to 1, the mean value theorem gives $g(\bar X_n) - g(\mu) = g'(\xi_n)(\bar X_n - \mu)$ there with $\xi_n \xrightarrow{p} \mu$, and the central limit theorem and Slutsky's theorem finish it. (This is the delta method of The Delta Method, Theorem 1, for a $g$ that need not be defined on the whole line.) Both limits are continuous, so both convergences are uniform, and the triangle inequality finishes the proof. $\square$

The check on the running sample. For $g = \ln$, the delta method's standard error of $\ln\bar X_n$ is $\hat\sigma_n/(\sqrt n\,\bar x) = 1.565/5.678 = 0.276$, and 2,000 resamples of the running sample (seed 1) gave a bootstrap standard error of 0.273. The two agree, as one expects when the bootstrap distribution is close to its normal limit; Theorem 7 itself is about distributions, and convergence in distribution alone does not make standard errors converge. Both estimate the true standard error, which the script computed from five sets of 200,000 samples of 30 (seeds 7 to 11) as 0.329. This sample's spread understates the population's, and no method that sees only the sample can know that.

How well it works on C-reactive protein

The theorems say the bootstrap distribution approaches the truth; they do not say how close it is at $n = 30$. The population makes the truth computable. For each sample size, the script found the true distributions of the root $R = \sqrt n(\bar X_n - \mu)$ and of the studentized mean $T = \sqrt n(\bar X_n - \mu)/s_n$ from 200,000 samples (seed 99). It then drew 30 data samples (seeds 1,000 to 1,029, the same seeds at each size), computed each one's bootstrap distribution from $B = 10{,}000$ resamples, and measured the Kolmogorov distance to the truth. For comparison it measured the distance of the usual approximations: for $R$ a normal with the plug-in standard deviation $\hat\sigma_n$ of the same sample, and for $T$ the standard normal and Student's $t$ with $n - 1$ degrees of freedom. Medians over the 30 samples:

$n$ $R$: bootstrap $R$: normal $T$: bootstrap $T$: normal $T$: $t_{n-1}$
10 0.309 0.306 0.213 0.271 0.256
30 0.173 0.171 0.124 0.217 0.211
100 0.116 0.113 0.056 0.124 0.123
400 0.048 0.047 0.018 0.059 0.059

The normal and $t$ columns for $T$ do not depend on the sample, since they compare a fixed curve with the true distribution. Three observations from this experiment:

  • For the unstudentized root, the bootstrap is no better than the normal. Both are off by about the same amount at every $n$. Each depends on the sample's $\hat\sigma_n$, and the error in $\hat\sigma_n$ is the main error of both. At $n = 30$ the sample standard deviation of CRP is very unreliable, which the wide spread of the distances reflects (interquartile range 0.095 to 0.310 for the bootstrap).
  • For the studentized mean, the bootstrap is much better. At $n = 100$ and $n = 400$ its distance is less than half that of the normal or $t$ approximation, and at $n = 30$ it is 0.124 against 0.217. The true distribution of $T$ is badly skewed: at $n = 30$ its 2.5% and 97.5% points are −5.06 and 1.29, nothing like the $t$ distribution's ±2.05. The bootstrap distribution of $T^*$ reproduces much of that skewness, and the normal cannot. Singh (1981) proved, for non-lattice populations, that the bootstrap is asymptotically more accurate than the normal approximation for the mean standardized by $\sigma$ (as his abstract states). The studentized root of this table, divided by $s_n$, is a different quantity, and the CRP values are recorded to 0.01 mg/L, which makes the population a lattice distribution; so the table is an observation of this experiment, not an instance of his theorem. The gain is largest at $n = 100$ and 400, where the bootstrap's distance is a half to a third of the normal's; at $n = 30$ it is 0.124 against 0.217, with an interquartile range over the 30 data sets of 0.105 to 0.159, and at $n = 10$ 0.213 against 0.271. Why studentizing produces the gain is the subject of Bootstrap Confidence Intervals.
  • Small samples stay hard. At $n = 10$ every approximation is far off. The true 2.5% point of $T$ is −7.58 at $n = 10$ and −2.80 at $n = 400$, against −2.26 and −1.97 for the $t$ distribution with 9 and 399 degrees of freedom; the bootstrap's improvement is partial when the sample cannot contain the tail.

Example (a median from thirty values). The bootstrap works for quantiles in large samples: Bickel and Freedman (1981) list the quantile process among the cases where it is asymptotically valid. At $n = 30$ it can still be far off. For the running sample, 2,000 resamples gave a bootstrap standard error of the median of 1.212 mg/L, while the true standard error of the median of 30 draws is about 0.58 (five sets of 200,000 samples, seeds 7 to 11, gave 0.580 to 0.586). The running sample has a gap between its fifteenth and sixteenth values, 1.58 and 2.51, exactly where the median sits, and the bootstrap medians jump across it. The Bootstrap Method measured the same unreliability of single-sample standard errors for a median of 25 exponential values.

Where the bootstrap fails

The proof of Theorem 5 shows what the bootstrap needs: a root whose distribution depends smoothly on $F$, and data whose largest values are small compared with $\sqrt n$ times the spread. The standard counterexample breaks the first condition outright.

Theorem 8 (the sample maximum). Let $X_1, \ldots, X_n$ be i.i.d. uniform on $(0, \theta)$ and $\hat\theta = X_{(n)}$ their maximum. (a) $P\big(n(\theta - X_{(n)})/\theta > t\big) = (1 - t/n)^n$ for $0 \le t \le n$, which tends to $e^{-t}$: the root $n(\theta - X_{(n)})/\theta$ converges in distribution to the exponential distribution with mean 1, which is continuous. (This is Problem 2 of the CLT article, with $\theta = 1$.) (b) For every data set whose maximum is unique, the bootstrap root $n(\hat\theta - X_{(n)}^*)/\hat\theta$, with $\hat\theta$ playing the part of $\theta$, equals 0 with probability $1 - (1 - 1/n)^n \ge 1 - e^{-1} = 0.6321$ under resampling. (c) Consequently the Kolmogorov distance between the bootstrap distribution and the true distribution of the root is at least 0.6321 for every $n$, and the bootstrap is not consistent.

Proof. (a) $X_{(n)} < \theta - \theta t/n$ exactly when all $n$ observations are, which has probability $(1 - t/n)^n$ by independence. Its limit is $e^{-t}$ (the limit $(1 + a/n)^n \to e^a$). (b) $X^*_{(n)} = X_{(n)}$ exactly when the largest observation is drawn at least once in the $n$ draws, and it is missed by all of them with probability $(1 - 1/n)^n$. Since $\ln(1 - u) \le -u$, $(1 - 1/n)^n \le e^{-1}$. (c) At $x = 0$, the bootstrap distribution function is at least 0.6321, while the true one is $P\big(n(\theta - X_{(n)}) \le 0\big) = P(X_{(n)} = \theta) = 0$. $\square$

The maximum depends on $F$ only through its upper end, which $\hat F_n$ never reaches: every bootstrap sample lies inside the original sample's range. The Bootstrap Method shows the resulting spike in 10,000 resamples. On the running sample the same arithmetic holds with $n = 30$: the bootstrap maximum equals the sample's 44.63 with probability $1 - (29/30)^{30} = 0.6383$ (10,000 resamples gave 0.6401). The corresponding event for real samples, that a sample of 30 contains the population's largest value, 182.82, has probability $1 - (1 - 1/5{,}146)^{30} = 0.0058$. The bootstrap describes the sample's maximum as more likely than not to recur (probability 0.64); the truth is that it almost never does.

Two other failures are cited, not proved, here.

  • Infinite variance. Athreya (1987) showed, for a population with infinite variance in the domain of attraction of a stable law, that the bootstrap distribution of the normalized mean has a random limit given the sample, so the bootstrap can fail for heavy tails (as his abstract states). The proof of Theorem 5 shows where its argument stops: with infinite variance, $\hat\sigma_n$ no longer converges, so part (ii) of Step 0 fails, and Lemma 1, which needs a finite second moment, is no longer available to make the largest observation negligible beside $\sqrt n\,\hat\sigma_n$. That locates the gap in this proof; the failure itself is Athreya's result.
  • Dependence. Resampling individual observations makes the bootstrap draws independent whatever the data were. For data that are not independent, such as time series or patients measured repeatedly, Steps 0 to 4 of Theorem 5 can still hold, so the bootstrap distribution still settles down, but to the wrong limit. It estimates the variance $\hat\sigma_n^2/n$ of a mean of independent draws, while the true variance of $\bar X_n$ includes every autocovariance of the series, so Step 5, the comparison with the truth, fails. Resampling Dependent and Clustered Data proves that the ordinary bootstrap estimates only the lag-0 part of the variance, and treats the block and cluster bootstraps that restore the dependence.

Bickel and Freedman (1981) give further counterexamples (their abstract says only that they do). The common thread is the one this article opened with: the plug-in principle is as good as the continuity of the functional being plugged into.

What is proved here, what is cited, what the experiment shows

Proved here: that the empirical distribution maximizes the likelihood among all distributions (from Gibbs' inequality); the Glivenko–Cantelli theorem (from the strong law for bounded variables); consistency of plug-in estimates of functionals continuous in the Kolmogorov distance, with the quantile as a case and the mean as a counterexample to continuity; the count of distinct bootstrap samples; the exact bootstrap mean and variance of a mean; that the largest of $n$ observations with a finite variance is small compared with $\sqrt n$; bootstrap consistency for the mean, the studentized mean and smooth functions of a mean, under a finite variance alone; and the failure of the bootstrap for the sample maximum.

Taken from other pages of the site: Gibbs' inequality; the quantile inequality $Q(u) \le x \iff u \le F(x)$ and the inverse transform (Random Variables and Distribution Functions, Theorems 2 and 3); the strong law under a finite fourth moment and the first Borel–Cantelli lemma; Lemma 5 and the steps of the characteristic function proof of the central limit theorem, the theorem on uniform convergence to a continuous limit, Slutsky's theorem and Corollary 1 there; the delta method.

Cited, not proved: the strong law of large numbers under a finite mean (Durrett, 2019, Theorem 2.4.1), used in Step 0 of Theorem 5; Lévy's continuity theorem, cited on the site's characteristic function page; the Dvoretzky–Kiefer–Wolfowitz inequality with Massart's constant (Massart, 1990, abstract), with the reduction to the uniform distribution proved here; and, from abstracts only, the asymptotic validity results of Bickel and Freedman (1981) and Singh (1981) and the infinite-variance failure of Athreya (1987).

What the experiment shows, for this population only: that the Glivenko–Cantelli distance fell in proportion to $1/\sqrt n$ from $n = 30$ to 6,400; that for the unstudentized root the bootstrap was no more accurate than the normal approximation, while for the studentized mean its Kolmogorov distance to the truth was a half to a third of the normal approximation's at $n = 100$ and 400; and that single-sample bootstrap standard errors at $n = 30$ can be far from the truth.

Worked problems

The problems are posed on the unit's running sample and on small exact cases, one for each main idea of the article. Every number is recomputed by the article's script, tools/experiments/statistics/plug-in-principle.py.

Problem 1 (an exact bootstrap distribution). The first three draws of the running sample were 4.48, 0.87 and 13.28. Find the exact bootstrap distribution of the mean of a bootstrap sample of size 3, and check Theorem 4 on it.

Solution. There are $3^3 = 27$ equally likely ordered bootstrap samples and $\binom{5}{3} = 10$ distinct multisets. Call the values $a = 4.48$, $b = 0.87$, $c = 13.28$. A multiset with one value three times arises from 1 ordered sample, one with two values the same from 3, and one with three different values from $3! = 6$. The means and their probabilities:

Bootstrap sample Mean Probability
$b, b, b$ 0.87 1/27
$a, b, b$ 2.07 3/27
$a, a, b$ 3.28 3/27
$a, a, a$ 4.48 1/27
$b, b, c$ 5.01 3/27
$a, b, c$ 6.21 6/27
$a, a, c$ 7.41 3/27
$b, c, c$ 9.14 3/27
$a, c, c$ 10.35 3/27
$c, c, c$ 13.28 1/27

The probabilities sum to 1. The mean of this distribution is $\bar x = (4.48 + 0.87 + 13.28)/3 = 6.21$, as Theorem 4 requires. The deviations of the three values from 6.21 are $-1.73$, $-5.34$ and $7.07$, so $\hat\sigma_3^2 = (2.9929 + 28.5156 + 49.9849)/3 = 27.1645$, and Theorem 4 predicts $\operatorname{Var}_*(\bar X^*) = 27.1645/3 = 9.0548$. Computing the variance directly from the table, in exact arithmetic, gives the same 9.0548, so the ideal bootstrap standard error is $\sqrt{9.0548} = 3.009$. The distribution is lumpy and skewed to the right, following the one large value: the bootstrap reproduces the shape of the sample, and with three values the sample has little shape to give.

Problem 2 (the bootstrap maximum). For the running sample of thirty, find the bootstrap probabilities that the maximum of a bootstrap sample is 44.63, that it is 19.01, and that it is at most 13.28.

Solution. They are 0.6383, 0.2354 and 0.1262. The three largest values are 44.63, 19.01 and 13.28, each appearing once. A bootstrap maximum is at most the $k$-th smallest value exactly when all 30 draws are among the $k$ smallest values, which has probability $(k/30)^{30}$. So $P_*(\max^* \le 13.28) = (28/30)^{30} = 0.1262$; $P_*(\max^* \le 19.01) = (29/30)^{30}$, and

$$P_*(\max\nolimits^* = 19.01) = (29/30)^{30} - (28/30)^{30} = 0.2354, \qquad P_*(\max\nolimits^* = 44.63) = 1 - (29/30)^{30} = 0.6383.$$

Nearly 90% of the bootstrap distribution sits on two values. A bootstrap standard error or interval for the maximum would describe these atoms, not the maximum of a new sample of 30, which, by Theorem 8's reasoning, almost never repeats this sample's 44.63.

Problem 3 (the AUC as a plug-in estimate). The area under the ROC curve of a test is $\theta = P(X > Y) + \frac12 P(X = Y)$, where $X$ is the score of a random case and $Y$ that of a random non-case, independent. Show that its plug-in estimate is the Mann–Whitney count of pairs, and compute it for cases scoring 3 and 5 and non-cases scoring 1, 3 and 4.

Solution. Plugging in replaces the distributions of $X$ and $Y$ by the empirical distributions $\hat F_1$ of the $n_1$ case scores and $\hat F_0$ of the $n_0$ non-case scores. Under $\hat F_1 \times \hat F_0$ the pair $(X, Y)$ is uniform on the $n_1 n_0$ pairs (case, non-case), so

$$T(\hat F_1, \hat F_0) = \frac{1}{n_1 n_0}\sum_{i=1}^{n_1}\sum_{j=1}^{n_0}\Big(\mathbf{1}\{x_i > y_j\} + \tfrac12\mathbf{1}\{x_i = y_j\}\Big),$$

the share of pairs in which the case scores higher, ties counted as one half. That is the Mann–Whitney statistic divided by $n_1 n_0$, the form in which ROC Curves for Diagnostic Tests computes the AUC. For the small case there are six pairs: the case scoring 3 beats 1, ties 3 and loses to 4, contributing $1 + \frac12 + 0$; the case scoring 5 beats all three. The plug-in AUC is $4.5/6 = 0.75$. For HbA1c as a screen for a diabetic fasting glucose, the same computation over 115 cases and 1,860 non-cases gives 0.8894, the value of that article. Its bootstrap, resampling cases and non-cases separately, is worked in Bootstrap Confidence Intervals.

Problem 4 (a distribution-free band). How many observations guarantee, by the Dvoretzky–Kiefer–Wolfowitz inequality, that $\hat F_n$ is within 0.05 of $F$ at every $x$ with probability at least 95%, whatever $F$ is?

Solution. 738 observations. The inequality bounds $P(d_K(\hat F_n, F) > \varepsilon)$ by $2e^{-2n\varepsilon^2}$ (put $\lambda = \sqrt n\,\varepsilon$). Requiring $2e^{-2n\varepsilon^2} \le 0.05$ means $2n\varepsilon^2 \ge \ln 40 = 3.6889$, so $n \ge 3.6889/(2 \times 0.05^2) = 737.8$, and the smallest whole number is 738. Since $1/\sqrt n$ governs the distance, halving the band to 0.025 needs four times as many. The CRP experiment fits this: at $n = 400$ the median distance was 0.039 and the 95% band 0.068.

Summary

  • A parameter is a functional $T(F)$ of the distribution; its plug-in estimate is $T(\hat F_n)$, with $\hat F_n$ the empirical distribution, which is the nonparametric maximum likelihood estimate of $F$.
  • The Glivenko–Cantelli theorem: $\sup_x\lvert\hat F_n(x) - F(x)\rvert \to 0$ with probability 1, for every $F$. The distance is of order $1/\sqrt n$, with the distribution-free 95% band $\sqrt{\ln(40)/(2n)}$.
  • A plug-in estimate is consistent if $T$ is continuous in that distance. Quantiles are, at points where $F$ increases; the mean is not, and its consistency rests on the law of large numbers instead.
  • The bootstrap estimates the sampling distribution $G_n(\cdot\,; F)$ of a root by $G_n(\cdot\,; \hat F_n)$, computed by Monte Carlo. For the mean, it reproduces the variance formula with divisor $n$.
  • Under a finite variance alone, the bootstrap distribution of $\sqrt n(\bar X^* - \bar X_n)$, of the studentized mean and of $\sqrt n(g(\bar X^*) - g(\bar X_n))$ for smooth $g$ converges uniformly to the true sampling distribution, with probability 1.
  • On CRP, the bootstrap was about as accurate as the normal approximation for the unstudentized mean and much more accurate for the studentized mean. It fails outright for the sample maximum, and it needs care with infinite variance and dependence.

What we have learned

The bootstrap is not a new principle. It is the plug-in principle, the oldest idea in estimation, applied to the sampling distribution of an estimate. It works for the same reason any plug-in estimate works: $\hat F_n$ converges to $F$, uniformly, and the quantity being estimated depends continuously on the distribution. For the mean, the continuity has to be earned from a finite variance, and the proof shows exactly where that variance is spent. For the maximum, there is no continuity to earn, and the bootstrap fails however large the sample.

The experiment raised a question that the consistency theorems cannot answer. Every root considered converges to the truth, yet the studentized root's bootstrap was two to three times closer to the truth than the normal approximation at $n = 100$ and 400 (less at smaller $n$), and the unstudentized root's was not. Which root to resample, and how to turn a bootstrap distribution into an interval, decide whether a 95% interval covers 95% of the time or 85%. That is the subject of Bootstrap Confidence Intervals: Percentile, Basic, Studentized and BCa.

References