The Problem Changes

In weeks 1 through 4, every method started from a known distribution \(F\). Monte Carlo integration drew \(X_1, \ldots, X_n \iid F\) and averaged; sampling methods (inverse transform, accept-reject, ratio of uniforms) each required \(F\) or its density. The error rate was \(O(n^{-1/2})\), dimension-free, and the CLT gave a confidence interval.

From here, \(F\) is unknown and the sample \(X_1, \ldots, X_n\) is all we have. The goal is the same: estimate a parameter \(\theta = T(F)\) and quantify how accurate the estimate is. The tool changes: replace \(F\) with the empirical distribution \(\hat F_n\).

The Statistical Inference Problem

The Fundamental Challenge. Given data \(X_1, \ldots, X_n \sim F\) and statistic \(\hat\theta = T(X_1, \ldots, X_n)\):

• We want: distribution of \(\hat\theta - \theta\) where \(\theta = T(F)\)
• We have: single realization of \(\hat\theta\)
• Classical approach: derive analytically (often impossible)
• Monte Carlo approach: simulate from \(F\) (but \(F\) is unknown)

\(T(F)\): the rule \(T\) applied to \(F\) itself (the mean of \(F\), the correlation under \(F\)), as \(\hat\theta\) applies it to the sample.

The Bootstrap Insight

The Bootstrap Insight (Efron, 1979). Replace the unknown \(F\) with the empirical distribution \(\hat{F}_n\):

\[\hat{F}_n(x) = \frac{1}{n}\sum_{i=1}^n \mathbf{1}\{X_i \leq x\}\]

where \(\mathbf{1}\{A\}\) is the indicator function, equal to \(1\) when \(A\) holds and \(0\) otherwise. Then simulate from \(\hat{F}_n\) to approximate the sampling distribution.

Two Worlds

“The population is to the sample as the sample is to the bootstrap samples.”

The Bootstrap Approximation

For smooth functionals \(T\):

\[\sqrt{n}(\hat\theta - \theta) \;\approx_{d}\; \sqrt{n}(\hat\theta^* - \hat\theta)\]

where the left side is distributed under \(P_F\) (over samples from \(F\)), the right side under \(P^*\) (over resamples, data fixed); \(\approx_d\): the two distributions are close.

Essentially, this says that the distribution of the recentered, rescaled statistic in the real world is close to the distribution of the same quantity in the bootstrap world.

The Law-School Data

The study. A study of admission practices covered \(N = 82\) American law schools. For each school it recorded two averages over the class entering in 1973: the mean LSAT score and the mean undergraduate GPA (Efron and Tibshirani, 1993).

The sample. We observe a random sample of \(n = 15\) of these schools. Each column is one school:

The unit of observation is a school. One point is one pair (mean LSAT, mean GPA), and the two coordinates of a pair belong together.

The Question We Ask of These Data

The parameter. How strongly do the two admission measures move together across law schools? We measure this by the correlation between LSAT and GPA over all \(82\) schools, \(\theta = T(F)\), where \(F\) is the joint distribution of the pair.

The estimate. The sample correlation of the \(15\) pairs is \(\hat\theta = T(\hat F_n) = 0.776\).

The problem. How far from \(\theta\) could an estimate from \(15\) points be? For a mean the answer is \(S/\sqrt{n}\). For a correlation the textbook formula \((1 - \hat\theta^2)/\sqrt{n - 3} = 0.115\) assumes bivariate normal data, and we have no reason to believe that here.

Why this dataset. We have the whole population of \(82\) schools, so we can check how well the bootstrap works against the truth. In practice we would not know \(\theta\) or the true sampling distribution.

The Sample within Its Population

The sample correlation is \(\hat\theta = 0.776\), and the population value is \(\theta = 0.760\). How accurate is \(\hat\theta\)?

What We Can Estimate

• Standard Error: \(\widehat{\text{SE}}(\hat\theta) = \sqrt{\frac{1}{B-1}\sum_{b=1}^B (\hat\theta^{*(b)} - \bar\theta^*)^2}\)
• Bias: \(\widehat{\text{Bias}}(\hat\theta) = \bar\theta^* - \hat\theta\) where \(\bar\theta^* = \frac{1}{B}\sum_{b=1}^B \hat\theta^{*(b)}\)
• Distribution: \(P^*(\hat\theta^* \leq t) \approx \frac{1}{B}\sum_{b=1}^B \mathbf{1}\{\hat\theta^{*(b)} \leq t\}\), the proportion of replicates at or below \(t\)

Notation

A star means computed from a resample; \((b)\) says which one.

The Sampling Distribution of \(\hat\theta\)

\(\theta\) is a fixed number. It has no distribution. For the law schools \(\theta = 0.760\), the correlation computed from all \(82\) schools.

\(\hat\theta\) is random, because the sample is. Another sample of \(15\) schools gives another \(\hat\theta\). The distribution of \(\hat\theta\) over repeated samples from \(F\) is the sampling distribution of \(\hat\theta\). The standard error \(\text{SE}_F(\hat\theta)\) is the standard deviation of that distribution.

In practice we have one sample and one \(\hat\theta\), so we never see the sampling distribution. Here we have the whole population, so we can build it: draw \(15\) schools from the \(82\), compute \(\hat\theta\), and repeat \(100000\) times. Each draw picks one of the \(82\) schools with probability \(1/82\), independently of the others, so a school can be drawn twice. This is \(X_1, \ldots, X_n \iid F\) with \(F\) the population of \(82\) schools.

The bootstrap runs the same recipe with the \(15\) schools we have in place of the \(82\): draw \(15\) from the \(15\), compute \(\hat\theta^*\), repeat \(B\) times.

Bootstrap and Sampling Distributions

Left: built from the \(15\) schools we have. Right: built from all \(82\), which is possible only here. The centers are \(\hat\theta\) and \(\theta\), so the bootstrap is asked to match the spread and the shape: \(\widehat{\text{SE}}_{\text{boot}} = 0.133\) against \(\text{SE}_F(\hat\theta) = 0.130\).

Monte Carlo Error in \(B\)

Each line is one bootstrap run on the same \(15\) law schools, and the runs differ only in their random resamples. Across runs \(\widehat{\text{SE}}_B\) has standard deviation \(0.0082\) at \(B = 200\) and \(0.0027\) at \(B = 2000\): ten times the work, about \(\sqrt{10}\) times the precision. Recall the same rate for \(n\) in week 1?

Consistency for the Mean

Theorem (Bootstrap Consistency for the Mean). Let \(\hat\theta = \bar{X}_n\) and assume \(\Var_F(X_1) = \sigma^2 < \infty\). Then:

\[\sup_t \left|P_F\!\left(\frac{\sqrt{n}(\bar{X}_n - \mu)}{\sigma} \leq t\right) - P^*\!\left(\frac{\sqrt{n}(\bar{X}_n^* - \bar{X}_n)}{S_n} \leq t\right)\right| \xrightarrow{P} 0\]

where \(S_n^2 = \frac{1}{n-1}\sum_{i=1}^n (X_i - \bar{X}_n)^2\); \(\mu = \E_F X_1\); \(\bar X_n^*\): the mean of one resample; \(P^*\): over the resampling, data fixed.

Essentially, this says the bootstrap distribution of the standardized mean converges uniformly to the true sampling distribution.

Proof idea. The CLT gives \(\sqrt{n}(\bar X_n - \mu)/\sigma \xrightarrow{d} \Normal(0,1)\). Given the data, \(X_1^*, \ldots, X_n^*\) are iid draws from \(\hat F_n\), a distribution with mean \(\bar X_n\) and variance \(\frac{n-1}{n}S_n^2\), and \(S_n^2\) settles at \(\sigma^2\) by the law of large numbers. A CLT in the bootstrap world then gives \(\sqrt{n}(\bar X_n^* - \bar X_n)/S_n \xrightarrow{d} \Normal(0,1)\) as well. We have two distribution functions converging to the same continuous limit, and convergence to a continuous limit is uniform in \(t\) (Polya’s theorem), thus the supremum of their difference vanishes.

Where the Bootstrap Fails

Example: \(\hat\theta = X_{(n)} = \max\{X_1, \ldots, X_n\}\) for \(X_i \sim \Uniform(0, \theta)\).

True distribution. \(P(X_{(n)} \leq x) = (x/\theta)^n\) for \(0 \leq x \leq \theta\), so \(P(n(\theta - X_{(n)})/\theta > t) = (1 - t/n)^n \to e^{-t}\). Thus \(n(\theta - X_{(n)})/\theta \xrightarrow{d} \Exp(1)\), a continuous distribution.

Bootstrap distribution. Each \(X_i^*\) is drawn independently from \(\{X_1, \ldots, X_n\}\), so \(P(X_i^* = X_{(n)}) = 1/n\). The bootstrap maximum \(X^*_{(n)} = \max_i X_i^*\) equals \(X_{(n)}\) when at least one draw hits it: \(P(X^*_{(n)} = X_{(n)}) = 1 - (1 - 1/n)^n \to 1 - e^{-1} \approx 0.632\). Thus the bootstrap analogue \(n(X_{(n)} - X^*_{(n)})/X_{(n)}\) equals zero with probability about \(0.632\), while the limit it should reproduce is continuous and puts no mass at zero.

The Failure in a Picture

With \(n = 50\), a proportion \(0.639\) of the bootstrap maxima equal \(X_{(n)}\). The theory gives \(1 - (1 - 1/n)^n = 0.636\).

The Bootstrap Works for Smooth Functionals

• The bootstrap replaces \(F\) with \(\hat F_n\) and runs Monte Carlo from there: the same \(O(B^{-1/2})\) convergence, the same averaging, with the data standing in for the population.
• Two errors: statistical (from \(\hat F_n\) in place of \(F\), controlled by \(n\)) and Monte Carlo (from \(B\) resamples, controlled by \(B\)).
• For smooth functionals of \(F\), the bootstrap distribution converges to the true sampling distribution.

A Confidence Interval Is a Procedure

Definition. A \(1-\alpha\) confidence interval for \(\theta\) is a pair of statistics \(L(\mathbf{X}) \leq U(\mathbf{X})\) with

\[P_F\bigl(L(\mathbf{X}) \leq \theta \leq U(\mathbf{X})\bigr) = 1 - \alpha \quad \text{for every } F \text{ in the model.}\]

The probability is over the sample \(\mathbf{X}\). The parameter \(\theta\) is a fixed number. The endpoints \(L\) and \(U\) are the random quantities.

Essentially, this says that if we repeated the whole experiment many times and built the interval each time, a fraction \(1 - \alpha\) of those intervals would contain \(\theta\).

After the data are in. The realized interval, say \((0.46, 0.96)\), either contains \(\theta\) or it does not. The \(95\%\) describes the procedure that produced it.

One Procedure, 100 Samples

Each segment is the interval \(\bar X \pm t_{n-1,\,0.975}\, S/\sqrt{n}\) from a fresh normal sample of \(n = 15\) (\(S\): sample standard deviation; \(t_{n-1,\,0.975}\): the \(0.975\) quantile of \(t_{n-1}\)), an exact \(95\%\) procedure. The two runs miss \(5\) and \(9\) times in \(100\): the count is a \(\Bin(100, 0.05)\) draw, and the \(95\%\) is the long-run fraction. In practice we hold one segment and never learn its color.

Nominal and Actual Coverage

Nominal coverage is the \(1 - \alpha\) that the formula promises under its assumptions. Actual coverage is \(P_F(L \leq \theta \leq U)\) under the distribution that generated the data, at the sample size we have. Coverage error is the difference between the two.

Exact

Actual equals nominal at every \(n\). The \(t\) interval for normal data is one example, and the next slide gives another.

Conservative

Actual exceeds nominal. The claim holds, and the interval is wider than it needs to be.

Liberal

Actual falls short of nominal. The interval claims more than it delivers.

A pivot is a function of the data and the parameter whose distribution does not depend on anything unknown. The \(t\) interval is exact for normal data because its pivot \((\bar X - \mu)/(S/\sqrt{n})\) has a \(t_{n-1}\) distribution, whatever \(\mu\) and \(\sigma\) are. A simulation of \(20000\) normal samples of \(n = 15\) agrees: \(0.950\). For any other \(F\) the \(t_{n-1}\) distribution is an approximation, and the actual coverage is whatever it turns out to be.

An Exact Interval for Exponential Data

Let \(X_1, \ldots, X_n\) be iid exponential with mean \(\mu\). Recall from week 2 that a sum of \(n\) independent exponentials is a Gamma variable, and that \(\chi^2_k = \Gam(k/2, 1/2)\)? Rescaling the sum gives a pivot:

\[\frac{2n\bar X}{\mu} = \frac{2}{\mu}\sum_{i=1}^n X_i \sim \chi^2_{2n}.\]

Its distribution is known and free of \(\mu\). Thus \(P\bigl(\chi^2_{2n,\,0.025} \leq 2n\bar X/\mu \leq \chi^2_{2n,\,0.975}\bigr) = 0.95\), and solving the two inequalities for \(\mu\) gives an exact \(95\%\) interval:

\[\left[\frac{2n\bar X}{\chi^2_{2n,\,0.975}},\; \frac{2n\bar X}{\chi^2_{2n,\,0.025}}\right].\]

Essentially, this says the exponential model hands us a pivot with a known distribution, as the normal model does. The interval is asymmetric about \(\bar X\): at \(n = 15\) it runs from \(0.64\,\bar X\) to \(1.79\,\bar X\).

Same Samples, Two Intervals

The same \(100\) exponential samples in both panels, \(n = 15\). The \(t\) interval is what we would compute without knowing \(F\). The exact interval needs the exponential model. Over \(20000\) samples the \(t\) interval covers \(0.912\) and the exact interval \(0.951\).

Both Sides of an Interval

An equal-tailed two-sided interval makes two promises:

\[P_F(\theta < L) = \alpha/2 \qquad \text{and} \qquad P_F(\theta > U) = \alpha/2.\]

For the exponential data, the \(t\) interval leaves \(\mu\) below its lower limit with probability \(0.005\) and above its upper limit with probability \(0.084\), each nominally \(0.025\). The total is off, and the split is off by more. The exact interval gives \(0.025\) and \(0.024\).

In the picture, all 11 misses of the \(t\) interval lie entirely below \(\mu\), and they are short. For a right-skewed \(F\) a sample with a small \(\bar X\) tends to have a small \(S\) as well, so its interval is shifted down and too short at once.

A one-sided statement, such as “the mean reduction is at least \(L\)”, rests on one of these two probabilities alone. This is where interval methods differ most, and it is the scale on which their accuracy is stated.

What We Ask of the Bootstrap

• Exactness came from knowing the distribution of a pivot: \(t_{n-1}\) under the normal model, \(\chi^2_{2n}\) under the exponential model. Both require knowing \(F\) up to its parameters, and in practice we do not.
• The bootstrap estimates the distribution of the pivot, or of \(\hat\theta\) itself, from the sample. No formula for that distribution is needed.
• A bootstrap interval is judged the way any interval is judged: by its actual coverage, on each side, at the sample sizes we face.
• The benchmark is the interval we would otherwise report, the \(t\) interval at \(0.912\) for the exponential mean. No bootstrap interval is exact. We ask how much of the coverage error it removes, and on which side.
• The four constructions that follow differ in what they bootstrap, and their coverage differs accordingly.

The Percentile Interval

Percentile Method. Use the bootstrap distribution quantiles directly:

\[\text{CI}_{\text{perc}} = \left[\hat\theta^*_{(\alpha/2)},\; \hat\theta^*_{(1-\alpha/2)}\right]\]

where \(\hat\theta^*_{(\alpha)}\) is the \(\alpha\)-quantile of \(\{\hat\theta^{*(1)}, \ldots, \hat\theta^{*(B)}\}\).

Justification. The interval is exact when some monotone transformation \(\phi\) makes \(\phi(\hat\theta)\) normal, centered at \(\phi(\theta)\), with constant variance. We never need to know \(\phi\).

Weakness. First-order accurate: one-sided coverage error \(O(n^{-1/2})\), with no correction for bias or skewness.

Strength. Respects monotone transformations: if \(\phi\) is monotone, \(\phi(\text{CI}_{\text{perc}}(\hat\theta)) = \text{CI}_{\text{perc}}(\phi(\hat\theta))\) (two-line argument in the notes).

The Basic (Pivotal) Interval

Derivation. If \(P(a \leq \hat\theta - \theta \leq b) = 1 - \alpha\), rearranging gives \(P(\hat\theta - b \leq \theta \leq \hat\theta - a) = 1 - \alpha\). We estimate the quantiles \(a\) and \(b\) of \(\hat\theta - \theta\) by those of \(\hat\theta^* - \hat\theta\), that is \(a \approx \hat\theta^*_{(\alpha/2)} - \hat\theta\) and \(b \approx \hat\theta^*_{(1-\alpha/2)} - \hat\theta\). Thus

\[\text{CI}_{\text{basic}} = \left[2\hat\theta - \hat\theta^*_{(1-\alpha/2)},\; 2\hat\theta - \hat\theta^*_{(\alpha/2)}\right]\]

Overshoot intuition. If bootstrap samples overshoot by amount \(d\), we expect the same overshoot in the real world, so we correct by \(-d\).

The Bootstrap-t Idea

The idea. Mimic the classical \(t\)-statistic approach:

\[t = \frac{\hat{\theta} - \theta}{\widehat{\text{SE}}(\hat{\theta})}\]

We do not know the distribution of \(t\), so we bootstrap it. The bootstrap studentized statistic is

\[t^{*(b)} = \frac{\hat{\theta}^{*(b)} - \hat{\theta}}{\widehat{\text{SE}}^{*(b)}}\]

where \(\theta\): the parameter; \(\hat\theta\): its estimate from the data; \(\widehat{\text{SE}}(\hat\theta)\): its estimated standard error; the \(^{*(b)}\) versions: defined on the next slide.

This requires computing \(\widehat{\text{SE}}^{*(b)}\) for each bootstrap sample.

Defining \(\hat\theta^{*(b)}\) and \(\widehat{\mathrm{SE}}^{*(b)}\)

\(\hat\theta = T(X_1, \ldots, X_n)\); \(\widehat{\text{SE}}(\cdot)\): a rule that turns a dataset into a standard-error estimate for \(T\) (a formula, the jackknife, or an inner bootstrap), so \(\widehat{\text{SE}}(\hat\theta) = \widehat{\text{SE}}(X_1, \ldots, X_n)\). On the \(b\)-th resample \(X_1^{*(b)}, \ldots, X_n^{*(b)}\), \(b = 1, \ldots, B\), the same two rules:

\[\hat\theta^{*(b)} = T\bigl(X_1^{*(b)}, \ldots, X_n^{*(b)}\bigr), \qquad \widehat{\text{SE}}^{*(b)} = \widehat{\text{SE}}\bigl(X_1^{*(b)}, \ldots, X_n^{*(b)}\bigr).\]

For the mean, \(\widehat{\text{SE}}^{*(b)} = S^{*(b)}/\sqrt{n}\), \(S^{*(b)}\) the standard deviation of the resample. The distribution of \(t\) is the unknown; the \(t^{*(b)}\) are draws from its bootstrap estimate.

Studentization

Why studentize. The basic interval assumes \(\hat\theta - \theta\) is pivotal (its distribution does not depend on \(F\)). This fails when:

• Variance depends on the parameter (e.g., Poisson, Binomial)
• Sample size is small
• Distribution is skewed

By dividing by \(\widehat{\text{SE}}^{*(b)}\), the bootstrap-t accounts for nonconstant variance and achieves second-order accuracy: \(O(n^{-1})\) vs \(O(n^{-1/2})\) for one-sided limits.

The quantile flip. The quantiles reverse in the confidence interval: if \(t^*\) is large and positive, \(\theta\) is probably smaller than \(\hat\theta\), so the upper quantile sets the lower bound.

Coverage Accuracy

Theorem (Hall, 1988). Under regularity conditions, the one-sided coverage error is:

• Percentile and Basic: \(O(n^{-1/2})\)
• Bootstrap-t and BCa: \(O(n^{-1})\)

Essentially, this says each endpoint of a bootstrap-t or BCa interval misses its nominal level by an amount of order \(1/n\), against \(1/\sqrt{n}\) for the percentile and basic intervals.

Two-sided intervals. In an equal-tailed two-sided percentile or basic interval the leading errors of the two endpoints cancel, so all four methods have two-sided coverage error \(O(n^{-1})\) (Hall, 1988). The difference shows in each endpoint separately, and in coverage at small \(n\).

BCa Preview

BCa (Bias-Corrected and Accelerated). Adjusts percentile endpoints for bias and skewness:

\[\text{CI}_{\text{BCa}} = \left[\hat\theta^*_{(\alpha_1)},\; \hat\theta^*_{(\alpha_2)}\right]\]

where

\[\alpha_1 = \Phi\!\left(\hat{z}_0 + \frac{\hat{z}_0 + z_{\alpha/2}}{1 - \hat{a}(\hat{z}_0 + z_{\alpha/2})}\right), \qquad \alpha_2 = \Phi\!\left(\hat{z}_0 + \frac{\hat{z}_0 + z_{1-\alpha/2}}{1 - \hat{a}(\hat{z}_0 + z_{1-\alpha/2})}\right)\]

where \(\Phi\) is the standard normal CDF and \(z_\alpha = \Phi^{-1}(\alpha)\).

The corrections. \(\hat{z}_0 = \Phi^{-1}\bigl(\#\{\hat\theta^{*(b)} < \hat\theta\}/B\bigr)\) corrects for median bias of the bootstrap distribution. \(\hat{a}\) corrects for the rate of change of the standard error (acceleration). When \(\hat z_0 = \hat a = 0\), BCa reduces to the percentile interval. Computed next week with the jackknife.

The Intervals on the Law Data

The basic interval \((0.59, 1.09)\) leaves the parameter space. The bootstrap-t \((-0.40, 0.98)\) is erratic at \(n = 15\): a resample with a tiny \(\widehat{\text{SE}}^*\) produces a huge \(t^*\). On Fisher’s scale \(\phi(\theta) = \tanh^{-1}\theta\) it shortens to \((-0.19, 0.95)\). The percentile and BCa intervals would not change under \(\phi\).

Coverage in a Skewed Problem

Recall actual against nominal coverage? Nominal 95%, mean of an exponential sample, \(n = 15\): bootstrap-t covers \(0.940\), BCa \(0.903\), percentile \(0.888\), basic \(0.870\). The percentile interval misses asymmetrically: \(0.093\) above against \(0.019\) below, each nominally \(0.025\).

Which Interval to Report

The two examples show both sides of the bootstrap-t. With the closed-form \(S^*/\sqrt{n}\) for a mean it has the best coverage of the four. With a jackknife \(\widehat{\text{SE}}^*\) for a correlation at \(n = 15\) it gives the least usable interval.

Standard Errors under Heteroscedasticity

Error standard deviation proportional to \(x\): the slope has true SE \(0.415\). Averaged over 200 datasets, pairs gives \(0.387\) and wild \(0.382\), while residual gives \(0.298\) and the classical formula \(0.305\).

Punchlines, and What Comes Next

• The bootstrap replaces \(F\) with \(\hat F_n\) and runs week-1 Monte Carlo from there. Two errors: statistical (from \(\hat F_n\), controlled by \(n\)) and Monte Carlo (from \(B\) resamples, controlled by \(B\)).
• It works for smooth functionals of \(F\). For non-smooth statistics like the sample maximum, the discrete support of \(\hat F_n\) prevents the bootstrap from approximating a continuous limit.
• The choice of interval matters: BCa and bootstrap-t give \(O(n^{-1})\) one-sided coverage error; percentile and basic give \(O(n^{-1/2})\).
• What you resample determines what you assume: pairs for heteroscedasticity, residuals for efficiency under homoscedasticity, wild when neither holds, parametric when the model is trusted.

The bootstrap is week-1 Monte Carlo with \(\hat F_n\) in place of \(F\). It asks for a smooth statistic and enough resamples. What remains is the choice of interval, and that choice decides the accuracy.