Unit 4.4 · about 6 h
75 / 324Bootstrap, permutation tests and multiple comparisons
Repeating an analysis changes the procedure being evaluated. Resampling, metric selection and early stopping need their own null distributions and error policies, not just a familiar test call.
- implement
- measure
You can now
- Derive the conditional sampling variance of a bootstrap mean and explain when permutation exchangeability holds.
- Implement Bonferroni and Benjamini-Hochberg, naming FWER and FDR and the assumptions behind each guarantee.
- Measure optional-stopping inflation and explain why selecting a winning estimate exaggerates apparent effects.
Covers
- Bootstrap and permutation tests
- Multiple comparisons, optional stopping and winner's curse
Study, in this order
4 steps
- 18.05 Class 24 reading: the empirical bootstrapMIT 18.05 - Inference practice
Sections 4 to 7: empirical distribution, resampling, bootstrap principle, percentile and basic intervals
Depth · Derive the conditional distribution for a three-point empirical population. Do not repeat the later paired-bootstrap implementation.
- SciPy: the unpaired permutation nullPermutation nulls and false discovery control
Notes, Unpaired statistics (
permutation_type='independent');alternativeparameter's exact and randomized p-value definitionsDepth · Read the null it states, one common distribution with labels assigned at random, and the exact-partition counting. Skip paired APIs and the numerical examples; do not reuse their randomly generated samples.
- SciPy: false discovery controlPermutation nulls and false discovery control
Notes on independence and positive regression dependence; Examples, the 15-hypothesis thrombolysis comparison of Bonferroni and Benjamini-Hochberg
Depth · Use the example to distinguish error criteria. Do not infer that FWER is the false-positive rate of one individual test.
- Johari, Pekelis and Walsh: why monitoring changes inferenceAlways Valid Inference
Version 3, July 16, 2019: Section 1, Introduction, pp. 1 to 3, especially Figure 1 and the continuous-monitoring motivation
Depth · Stop before the technical construction of always-valid tests. Understand the failure and the need for a predeclared fixed horizon or a valid sequential procedure.
Focus on
- Condition on observed data: each bootstrap draw has mean \(\bar{X}\) and variance \(\sum (x_i - \bar{X})^2/n\). Independent draws of size \(n\) therefore give \(\operatorname{Var}^*(\bar{X}^*) = \sum (x_i - \bar{X})^2/n^2\). This approximates a sampling variance; it does not create new population information.
- A permutation null makes labels exchangeable, for example under identical independent group distributions or a sharp no-effect randomization null. Equal means alone do not make unequal-variance observations exchangeable.
- Bonferroni rejects at \(\alpha/m\) and controls \(\text{FWER} = P(V \ge 1)\) by the union bound for valid marginal p-values, without independence. BH sorts p-values, finds the largest \(k\) with \(p(k) \le kq/m\), and rejects ranks 1 to \(k\). It controls \(\text{FDR} = \mathbb{E}[V/\max(R, 1)]\) under independence or suitable positive dependence, not arbitrary dependence.
- The maximum of noisy estimates is selected for positive noise as well as signal. Its original pointwise interval is not automatically a post-selection interval. Repeated looks also select noise, even though successive cumulative tests are dependent.
Reproduce closed-book
[0, 1, 2]: 2/9. Enumerate all 27 ordered length-three resamples in NumPy float64 with itertools.product(range(3), repeat=3), index the data array and take each row mean. Their mean is 1 and variance with ddof=0 is 0.222222; absolute difference from 2/9 was below 1e-15. Separately implement Bonferroni and the BH step-up rule for \(p\) = [0.001, 0.012, 0.020, 0.080, 0.200], \(\alpha\) = \(q\) = 0.05. Bonferroni rejects only rank 1; BH rejects ranks 1 to 3. Compute BH adjusted values by reverse cumulative minima of \(m p(i)/i\), capped at 1: displayed to six decimals they are [0.005, 0.030, 0.033333, 0.100, 0.200]. Compare the unrounded values with scipy.stats.false_discovery_control(p, method='bh'), requiring infinity-norm difference below 1e-12. Finally use rng = numpy.random.default_rng(44); draw rng.normal(0, 1, size=(10000, 200)) once in float64. Compute cumulative row sums at \(n = 10, 20, \ldots, 200\) divided by \(\sqrt{n}\); reject when abs(Z) > scipy.stats.norm.ppf(0.975). Rejection at the final look is 0.0516, versus 0.2495 for any look. Against the fixed-horizon target 0.05, allow absolute Monte Carlo error 0.01. Do not compare the any-look rate to \(1 - 0.95^{20}\): these looks are dependent. Seeded values came from NumPy 2.5.4 with SciPy 1.18.1.Traps
- Permuting labels to test only equal means when variances or sampling schemes differ. The exchangeability null is stronger.
- Treating BH as a guarantee that at most q of this particular rejection list is false. It bounds an expectation over repeated analyses.
- Reporting only the first significant look or best metric, then quoting its original fixed-analysis error rate.
Practice
18.05 Problem Set 9, Problem 2: the interrupted coin experiment
Problem 2(a to d), p. 1: fixed flips, stopping at the third head, partial data and Bayesian likelihoods
Attempt before reading the official solutions linked on the course Problem Sets page. The section mini-project should add bootstrap coverage, Bonferroni/BH simulations and selection of the largest noisy metric; these are not checked by this coin problem.
Self-test
-
Prove Bonferroni control and identify where independence is used.
Let \(I_0\) contain the \(m_0\) true nulls. Valid p-values give \(P(p_i \le \alpha/m) \le \alpha/m\) for each \(i\) in \(I_0\). The union bound gives \(P(\text{any true null rejected}) \le \sum_{I_0} \alpha/m = m_0\alpha/m \le \alpha\), since \(m_0 \le m\). No independence is used. The family and thresholds must describe the full analysis, not a selected subset. -
If all hypotheses are null, how are FDR and FWER related?
\(V = R\), so \(V/\max(R, 1)\) is 1 exactly when any hypothesis is rejected and 0 otherwise. Hence \(\text{FDR} = P(R > 0) = \text{FWER}\). With genuine alternatives present they need not coincide. -
Why can a percentile bootstrap fail for the endpoint of a uniform distribution?
Every resampled maximum is at most the observed maximum. The true upper endpoint exceeds the observed maximum almost surely in a continuous uniform sample, so a percentile interval made only from resampled maxima cannot cover it. The plug-in bootstrap fails for this boundary statistic. -
What must a sequential alternative to fixed-horizon inference guarantee?
It must control the probability of a false rejection over the allowed data-dependent stopping times, not merely at each single fixed n. Looking early for safety does not license an ordinary fixed-n efficacy claim at the selected stopping time.
Completion criterion
Stop when
You derive and enumerate the bootstrap variance, match the BH oracle, reproduce stopping inflation, and solve the coin problem while naming the error controlled by each rule.
Mark passed, then open 4.5 Only mark this when you can do it without notes.Leads to
- 5.6 Paired bootstrap, permutation tests and multiplicity Apply these sampling and error-control principles to paired model comparisons.
Comes after
- 3.6 Laws of large numbers, CLT, concentration and Monte CarloBootstrap and permutation resampling inherit these Monte Carlo error bars.
Resources for this unit
- MIT 18.05 - Inference practice Use classes 17-20, 22-24 and 26 with their problem sets for tests, intervals, bootstrap and regression.
- Always Valid Inference Use the introduction and worked motivation to understand optional-stopping failure. Reproducing the theory is outside this gate.
- Permutation nulls and false discovery control Read
permutation_testNotes, Unpaired statistics, for exchangeability and exact partitions;false_discovery_controlNotes and the named thrombolysis example for Bonferroni and Benjamini-Hochberg. Use as an independent implementation oracle, not as a substitute for stating assumptions.
Also in this section
- MIT 14.310x - Data Analysis for Social Scientists Follow lectures 11-15, 17-20 and 22 with matching slides and problem sets for inference, regression, causality and experiment design.
- Causal Inference: What If Read Chapters 1-3 and 6-8 for causal effects, DAGs, confounding, selection bias and identification reasoning.
- Patterns of trustworthy experimentation Read after the course to connect health checks, guardrails and statistical interpretation to production launch decisions.
- Probabilistic Machine Learning: An Introduction Use the April 18, 2025 online edition: Sections 4.2.3 to 4.2.5, 4.5.1 and 4.6.4.1 for Bernoulli and Gaussian MLE/MAP; the definition and central intervals in 4.6.6; 2.1.2 and 11.7.4 for predictive uncertainty. Exercises 4.1 and 4.2 supply derivation practice.
- Probability calibration: the statistical property Read the opening calibration definition, the proper-scoring-rule note, and Section 1.16.1, Calibration curves. Stop before recalibration methods; the later Classical ML unit implements them.