45.02.05 · mathematical-statistics / 02-hypothesis-testing-confidence

Multiple Testing: Familywise Error, the False Discovery Rate, and Benjamini-Hochberg

shipped3 tiersLean: none

Anchor (Master): Lehmann & Romano 2005 Testing Statistical Hypotheses (3rd ed., Springer) Ch. 9; Benjamini & Hochberg 1995 (JRSS-B); Benjamini & Yekutieli 2001 (Annals of Statistics, FDR under dependence); Efron 2010 Large-Scale Inference (Cambridge) Ch. 4-5 (local FDR, the two-groups empirical-Bayes model)

Intuition Beginner

Run one hypothesis test at a 5-in-100 false-alarm rate and you accept a small chance of crying wolf. Run a thousand tests at the same rate and, even if nothing is going on anywhere, you expect about fifty false alarms. This is the multiplicity problem: error rates that are comfortable for a single test become a flood when you test many things at once. Genomics screens hundreds of thousands of genes; a brain scan tests tens of thousands of locations. Without a fix, the "discoveries" are mostly noise.

There are two honest ways to tighten the rules. The first asks: what is the chance of making even one false alarm across the whole batch? Keep that chance below 5 in 100 and you are being very strict. This is the familywise error rate, and the simplest way to control it is to divide your per-test budget by the number of tests.

The second way is gentler. Instead of forbidding any false alarm, it asks: of the things I flag as discoveries, what fraction are false? If you flag a hundred genes and can tolerate that about five of them are wrong, you control the false discovery rate. This trades a little purity for a lot more detection power, which is why it took over large-scale science.

The Benjamini-Hochberg rule is the recipe for the second way. Sort your p-values from smallest to largest, compare each to a sliding bar that rises as you go down the list, and reject everything up to the last one that clears its bar.

Visual Beginner

Figure: a staircase plot. The horizontal axis is the rank of a p-value (1st smallest, 2nd smallest, and so on, up to m). The vertical axis is the p-value. The sorted p-values are plotted as dots that climb from low-left to high-right. A straight line through the origin with slope q/m is drawn — the sliding bar. Wherever a dot sits below the line, that p-value clears its bar. Benjamini-Hochberg finds the largest rank whose dot is still under the line and rejects every hypothesis up to and including that rank, even ones whose own dot briefly poked above the line.

 p-value
  |                                          . p_(m)
  |                                      .
  |                              .   /  (BH line: slope q/m)
  |                          .     /
  |                      .       /
  |                  .         /
  |              .     o     /   <- last dot below the line (cutoff rank)
  |          .   o   /
  |      o   o   /
  |  o   o   /
  +------------------------------------------------> rank i = 1, 2, ..., m
       dots below the line clear the sliding bar i*q/m

Worked example Beginner

You test $m = 10$ hypotheses and want the false discovery rate held to $q = 0.05$ . The ten p-values, sorted from smallest to largest, are: $0.001, 0.008, 0.012, 0.018, 0.030, 0.041, 0.060, 0.200, 0.450, 0.800$ .

Step 1. Build the sliding bar. For rank $i$ the bar is $i \times q / m = i \times 0.05/10 = i \times 0.005$ . So the bars are $0.005, 0.010, 0.015, 0.020, 0.025, 0.030, 0.035, 0.040, 0.045, 0.050$ .

Step 2. Compare each p-value to its bar. Rank 1: $0.001 \leq 0.005$ , clears. Rank 2: $0.008 \leq 0.010$ , clears. Rank 3: $0.012 \leq 0.015$ , clears. Rank 4: $0.018 \leq 0.020$ , clears. Rank 5: $0.030 > 0.025$ , fails. Rank 6: $0.041 > 0.030$ , fails. The rest fail too.

Step 3. Find the largest rank that cleared. That is rank 4. The rule rejects everything up to rank 4, so the four smallest p-values are declared discoveries.

Step 4. Compare with Bonferroni. Bonferroni would reject only p-values below $q / m = 0.005$ , catching just rank 1. Benjamini-Hochberg found four discoveries where Bonferroni found one.

What this tells us. The step-up rule is more generous than dividing by $m$ , because it lets the bar rise as more small p-values pile up. The price is a different, weaker promise: not "almost surely no false alarm" but "on average, at most 5 in 100 of my discoveries are false."

Check your understanding Beginner

Exercise (easy, multiple choice).

The false discovery rate is best described as:

A. the probability of at least one false alarm across the whole batch of tests B. the expected fraction of false alarms among the hypotheses you declare discoveries C. the probability that a single fixed null hypothesis is true D. the number of tests you run

Hint

It is a ratio: false discoveries divided by total discoveries, averaged over many repetitions.

Answer

B. the expected fraction of false alarms among the hypotheses you declare discoveries.

Feedback-correct: correct — the FDR averages the proportion of rejections that are mistakes. Feedback-wrong: option A describes the familywise error rate, a stricter quantity; the FDR is about the purity of the discovery list, not whether any single error occurs.

Formal definition Intermediate+

Test $m$ null hypotheses $H_{1}, \dots, H_{m}$ simultaneously, producing p-values $p_{1}, \dots, p_{m}$ . Let $I_{0} \subseteq {1, \dots, m}$ index the true nulls, with $m_{0} = ∣ I_{0} ∣$ , and write $π_{0} = m_{0} / m$ . A multiple-testing procedure maps the p-value vector to a rejection set $R \subseteq {1, \dots, m}$ (the discoveries). The standard assumption on the data side is that each true-null p-value satisfies $P (p_{i} \leq u) \leq u$ for all $u \in [0, 1]$ (super-uniform: it is $Unif [0, 1]$ when the null statistic is continuous, the calibration of 45.02.01, and stochastically larger when there are atoms).

Classify the outcomes by a confusion table over the $m$ hypotheses. Let $R = ∣ R ∣$ be the number of rejections, $V = ∣ R \cap I_{0} ∣$ the number of false rejections (true nulls rejected), and $S = R - V$ the number of true rejections.

Definition (familywise error rate). The familywise error rate is the probability of at least one false rejection,

FWER = P (V \geq 1) .

A procedure controls FWER at level $α$ in the strong sense if $FWER \leq α$ for every configuration of which nulls are true; weak control requires the bound only when all nulls are true ( $m_{0} = m$ ).

Definition (false discovery proportion and rate). The false discovery proportion is the realized fraction of mistakes among discoveries, with the convention that no discoveries means no error,

FDP = \frac{V}{max ( R , 1 )} = {V / R 0 R > 0, R = 0.

The false discovery rate is its expectation, $FDR = E [FDP]$ . The positive FDR conditions on making at least one discovery: $pFDR = E [V / R ∣ R > 0]$ ^{[Benjamini & Hochberg 1995]}.

Order the p-values as $p_{(1)} \leq p_{(2)} \leq \dots \leq p_{(m)}$ with associated hypotheses $H_{(1)}, \dots, H_{(m)}$ .

Definition (the procedures). Fix a target level $α$ (for FWER) or $q$ (for FDR).

Bonferroni: reject $H_{i}$ whenever $p_{i} \leq α / m$ .
Šidák: under independence, reject $H_{i}$ whenever $p_{i} \leq 1 - (1 - α)^{1/ m}$ .
Holm (step-down): let $k$ be the smallest index with $p_{(k)} > α / (m - k + 1)$ ; reject $H_{(1)}, \dots, H_{(k - 1)}$ (reject all if no such $k$ ).
Hochberg (step-up): let $k$ be the largest index with $p_{(k)} \leq α / (m - k + 1)$ ; reject $H_{(1)}, \dots, H_{(k)}$ .
Benjamini-Hochberg (linear step-up): let

\hat{k} = max {i : p_{(i)} \leq \frac{i}{m} q}

(set $\hat{k} = 0$ if the set is empty) and reject $H_{(1)}, \dots, H_{(\hat{k})}$ .

The Holm/Hochberg thresholds $α / (m - k + 1)$ relax the Bonferroni cutoff as one moves through the ordered list; the Benjamini-Hochberg threshold $i q / m$ relaxes it far more aggressively, which is the source of its power.

Counterexamples to common slips

FDR is not FDP. The proportion $V / max (R, 1)$ is random; only its expectation is controlled. A single experiment can have an FDP well above $q$ ; the guarantee is on the long-run average. The FDP can be controlled too (its quantiles), but that is a different, stronger procedure.
Step-up is not step-down. Holm scans from the smallest p-value and stops at the first failure; Hochberg and Benjamini-Hochberg scan from the largest and reject up to the last success. They can reject different sets; conflating the directions gives the wrong cutoff.
Bonferroni controls FWER, not FDR, and Benjamini-Hochberg controls FDR, not FWER. A procedure tuned to one criterion gives only the weaker guarantee for the other. Reporting a Benjamini-Hochberg discovery list as if no false positive can have occurred misstates what was controlled.

Key theorem with proof Intermediate+

The signature result is that the Benjamini-Hochberg linear step-up procedure controls the false discovery rate, with the bound carrying the unknown proportion of true nulls as a free dividend.

Theorem (Benjamini-Hochberg, 1995). Suppose the p-values of the true nulls are mutually independent and independent of the false-null p-values, and each true-null p-value is super-uniform ( $P (p_{i} \leq u) \leq u$ ). Then the linear step-up procedure at level $q$ satisfies

FDR = E [\frac{V}{max ( R , 1 )}] \leq \frac{m _{0}}{m} q \leq q .

Proof. The argument decomposes the FDR over the true nulls and over the possible final cutoff sizes, then uses independence to pin one true-null p-value at a time.

Write the FDR as a sum over true nulls and over the realized number of rejections $R$ :

FDR = E [\frac{V}{max ( R , 1 )}] = i \in I_{0} \sum r = 1 \sum m \frac{1}{r} P (p_{i} \leq \frac{r}{m} q, R = r),

because $V = \sum_{i \in I_{0}} 1 {H_{i} rejected}$ , and when $R = r > 0$ the linear step-up procedure rejects $H_{i}$ exactly when $p_{i} \leq p_{(r)} = \frac{r}{m} q$ at the determined cutoff; the term $R = 0$ contributes nothing since then $V = 0$ .

The key combinatorial fact is the self-consistency of the cutoff. Fix a true null $i$ and consider the procedure run on the full vector. Let $R^{(i)} (t)$ denote the number of rejections of the linear step-up procedure applied to the modified vector in which $p_{i}$ is replaced by the value $t$ . The crucial monotonicity is: on the event ${p_{i} \leq \frac{r}{m} q, R = r}$ , the total number of rejections is exactly $r$ , and freezing $p_{i}$ at any value $\leq \frac{r}{m} q$ leaves the final cutoff at rank $r$ . Concretely, the event ${R = r, p_{i} \leq \frac{r}{m} q}$ coincides with the event ${p_{i} \leq \frac{r}{m} q} \cap A_{r}^{(i)}$ , where $A_{r}^{(i)} = {$ the procedure run on the other $m - 1$ p-values together with a value $\leq \frac{r}{m} q$ in slot $i$ rejects exactly $r}$ depends only on ${p_{j} : j \neq = i}$ .

Now use independence. Since $p_{i}$ is independent of ${p_{j} : j \neq = i}$ , hence of the event $A_{r}^{(i)}$ ,

P (p_{i} \leq \frac{r}{m} q, R = r) = P (p_{i} \leq \frac{r}{m} q, A_{r}^{(i)}) = P (p_{i} \leq \frac{r}{m} q) P (A_{r}^{(i)}) \leq \frac{r}{m} q P (A_{r}^{(i)}),

where the last step is super-uniformity of the true null $p_{i}$ . Substituting,

FDR \leq i \in I_{0} \sum r = 1 \sum m \frac{1}{r} \cdot \frac{r}{m} q P (A_{r}^{(i)}) = \frac{q}{m} i \in I_{0} \sum r = 1 \sum m P (A_{r}^{(i)}) .

For each fixed $i$ the events ${A_{r}^{(i)}}_{r = 1}^{m}$ partition the sample space according to the resulting number of rejections (the procedure with $p_{i}$ frozen small rejects some number between $1$ and $m$ ), so $\sum_{r = 1}^{m} P (A_{r}^{(i)}) = 1$ . Hence the inner sum is $1$ for each of the $m_{0}$ true nulls, giving

FDR \leq \frac{q}{m} i \in I_{0} \sum 1 = \frac{q}{m} m_{0} = \frac{m _{0}}{m} q . □

Bridge. This theorem builds toward the dependence theory of the master section, where the same step-up procedure is shown to retain its bound under positive regression dependence and to need a logarithmic correction under arbitrary dependence, and it appears again in the empirical-Bayes reading of 45.03.03, where the cutoff $p_{(\hat{k})} = \frac{k ^}{m} q$ is recognized as an estimated local false discovery rate. This is exactly the multiplicity-corrected sharpening of the single-test calibration of 45.02.01: each summand uses that one true-null p-value is super-uniform, the very fact that gives a single test its size, now aggregated across a family. The central insight is that the conservative slack is precisely the unknown true-null fraction $m_{0} / m$ , so the procedure is automatically adaptive — it spends its full budget $q$ only when every hypothesis is null, and the foundational reason the bound holds is the self-consistency identity that lets one freeze a single true-null p-value while the rest determine the cutoff. Putting these together, FWER control is the special case of demanding the discovery list be error-free, the bridge is the confusion-table decomposition $V / max (R, 1)$ , and the proof technique generalises to the positive-dependence case by replacing independence with a monotonicity of the conditional cutoff law.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that Šidák's cutoff $1 - (1 - α)^{1/ m}$ is slightly larger (less stringent) than Bonferroni's $α / m$ , and that under independence of all $m$ true nulls the Šidák procedure controls FWER at exactly $α$ when each p-value is uniform.

Hint

For the comparison use the inequality $(1 - x)^{1/ m} \leq 1 - x / m$ . For the control use independence to multiply the per-test acceptance probabilities.

Answer

Comparison: by Bernoulli/convexity $(1 - α)^{1/ m} \leq 1 - α / m$ , so $1 - (1 - α)^{1/ m} \geq α / m$ ; the Šidák cutoff dominates Bonferroni's. Control: with all nulls true, uniform and independent, $FWER = 1 - P (no false alarm) = 1 - \prod_{i = 1}^{m} P (p_{i} > c) = 1 - (1 - c)^{m}$ with $c = 1 - (1 - α)^{1/ m}$ . Then $(1 - c)^{m} = ((1 - α)^{1/ m})^{m} = 1 - α$ , so $FWER = α$ exactly. The gain over Bonferroni is the difference between $1 - (1 - α)^{m}$ -type exactness and the union-bound slack, which is small for small $α$ .

Exercise 4 (medium, symbolic).

Prove that Holm's step-down procedure controls FWER at level $α$ under arbitrary dependence.

Hint

Let $i_{0}$ be the true null with the smallest p-value among true nulls, of rank $j$ in the full ordering. On the event of any false rejection, bound $p_{i_{0}}$ from below by its Holm threshold and apply the union bound to ${p_{i_{0}} \leq α / m_{0}}$ .

Answer

Suppose a false rejection occurs; let $i_{0} = ar g min_{i \in I_{0}} p_{i}$ be the first-rejected true null, sitting at some position $j$ in the global order, so $p_{i_{0}} = p_{(j)}$ . For $i_{0}$ to be rejected, every step up to $j$ must have cleared, in particular $p_{(j)} \leq α / (m - j + 1)$ . Among the ranks $1, \dots, j$ at most $j - 1$ belong to false nulls (since $i_{0}$ is the smallest true-null p-value, all true nulls have rank $\geq j$ ), so $j - 1 \leq m - m_{0}$ , i.e. $m - j + 1 \geq m_{0}$ . Hence $p_{i_{0}} \leq α / (m - j + 1) \leq α / m_{0}$ . Therefore ${V \geq 1} \subseteq ⋃_{i \in I_{0}} {p_{i} \leq α / m_{0}}$ , and the union bound gives $FWER \leq \sum_{i \in I_{0}} P (p_{i} \leq α / m_{0}) \leq m_{0} \cdot α / m_{0} = α$ . No independence was used. Holm is uniformly more powerful than Bonferroni because its thresholds $α / (m - k + 1) \geq α / m$ are never smaller.

Exercise 5 (medium, symbolic).

In the Benjamini-Hochberg FDR proof, verify the claimed identity $\sum_{r = 1}^{m} P (A_{r}^{(i)}) = 1$ for a fixed true null $i$ , and explain why $A_{r}^{(i)}$ is independent of $p_{i}$ .

Hint

$A_{r}^{(i)}$ is defined by running the procedure with $p_{i}$ replaced by a small frozen value, so it depends only on the other coordinates and partitions by the resulting rejection count.

Answer

By construction $A_{r}^{(i)}$ is the event that the linear step-up procedure, run with $p_{i}$ set to a value at or below the cutoff and the other $m - 1$ p-values at their observed values, rejects exactly $r$ hypotheses. With $p_{i}$ pinned small the procedure always rejects at least one (that frozen index clears the lowest bar), so the number rejected is a deterministic function of ${p_{j} : j \neq = i}$ taking some value in ${1, \dots, m}$ . The events ${A_{r}^{(i)}}_{r}$ are the level sets of that function, hence disjoint with union the whole space: $\sum_{r} P (A_{r}^{(i)}) = 1$ . Each $A_{r}^{(i)}$ is $σ ({p_{j} : j \neq = i})$ -measurable, and $p_{i} ⊥ {p_{j} : j \neq = i}$ by the independence hypothesis, so $A_{r}^{(i)} ⊥ p_{i}$ , justifying the factorization in the proof.

Exercise 6 (hard, symbolic).

Prove Simes' inequality: if $p_{1}, \dots, p_{m}$ are independent and each true-null p-value is uniform (take all nulls true), then $P (\exists i : p_{(i)} \leq i α / m) \leq α$ — equivalently $P (⋂_{i} {p_{(i)} > i α / m}) \geq 1 - α$ . (This is the validity of the Simes global test and underlies Hochberg's step-up FWER control.)

Hint

Condition on the largest order statistic and induct on $m$ , or use the known result that for i.i.d. uniforms $P (\forall i, U_{(i)} > i α / m) = 1 - α$ via an exchangeability / ballot-type argument.

Answer

Let $U_{(1)} \leq \dots \leq U_{(m)}$ be the order statistics of $m$ i.i.d. $Unif [0, 1]$ . Claim: $P (U_{(i)} > i α / m for all i) = 1 - α$ . Induct on $m$ . Condition on $U_{(m)} = t$ . Given the maximum is $t$ , the remaining $m - 1$ values are i.i.d. $Unif [0, t]$ with order statistics $t \cdot V_{(1)} \leq \dots \leq t \cdot V_{(m - 1)}$ for $V$ 's i.i.d. uniform on $[0, 1]$ . The event ${U_{(i)} > i α / m, i < m}$ becomes ${V_{(i)} > i α / (m t)}$ ; one checks the boundary condition closes the induction and the marginal of $U_{(m)}$ (density $m t^{m - 1}$ ) integrates the conditional survival to give exactly $1 - α$ (the standard Simes computation). Hence $P (\exists i : p_{(i)} \leq i α / m) = 1 - (1 - α) = α$ under all-null independence, and $\leq α$ when some nulls are false (fewer ways to violate). The inequality is the validity of the Simes test and the engine behind Hochberg's step-up FWER control.

Exercise 7 (hard, symbolic).

Show that the Benjamini-Hochberg bound is tight: construct a configuration (independent p-values) where $FDR = (m_{0} / m) q$ exactly, so the slack $m_{0} / m$ cannot be removed without further assumptions.

Hint

Make the $m - m_{0}$ false nulls have p-values that are effectively $0$ (perfect signal), and let the $m_{0}$ true nulls be uniform. Compute the FDR.

Answer

Let the $m_{1} = m - m_{0}$ false nulls return $p = 0$ (deterministically rejected) and the $m_{0}$ true nulls be i.i.d. uniform. With $m_{1}$ guaranteed rejections, the linear step-up cutoff at total count $r$ requires $p_{(r)} \leq r q / m$ . A true null at value $u$ joins the rejection set when $u \leq (m_{1} + (its rank among rejected nulls)) q / m$ . A direct computation (or the proof specialized to this case, where each $A_{r}^{(i)}$ degenerates appropriately) gives $FDR = (m_{0} / m) q$ : each of the $m_{0}$ uniform nulls contributes expected $V / R$ summing to exactly $(m_{0} / m) q$ because the false nulls absorb no slack. Hence the constant $m_{0} / m$ is attained, and an unqualified bound below $(m_{0} / m) q$ is impossible without estimating $m_{0}$ (adaptive procedures do exactly this).

Exercise 8 (hard, short-answer).

Explain, with the two-groups model, why the local false discovery rate $fdr (z) = π_{0} f_{0} (z) / f (z)$ is a posterior probability, and how it relates to the tail-area $Fdr (z)$ that Benjamini-Hochberg controls. Rubric: name the mixture, identify the posterior, and state the averaging relation.

Hint

Each case is null with prior probability $π_{0}$ and density $f_{0}$ , or non-null with density $f_{1}$ ; the observed statistic has marginal $f = π_{0} f_{0} + π_{1} f_{1}$ .

Answer

Two-groups model: each case is null with prior probability $π_{0}$ (statistic density $f_{0}$ ) or non-null with probability $π_{1} = 1 - π_{0}$ (density $f_{1}$ ), giving marginal $f (z) = π_{0} f_{0} (z) + π_{1} f_{1} (z)$ . By Bayes, the posterior probability that a case with statistic $z$ is null is $P (null ∣ Z = z) = π_{0} f_{0} (z) / f (z) = fdr (z)$ — the local FDR. Its tail-average is $Fdr (z) = P (null ∣ Z \leq z) = π_{0} F_{0} (z) / F (z)$ , the expected proportion of nulls among cases at least as extreme as $z$ . The Benjamini-Hochberg cutoff $p_{(\hat{k})} = \hat{k} q / m$ is an empirical estimate of the threshold where $Fdr = q$ (with $\overset{π}{^}_{0} \leq 1$ ), so Benjamini-Hochberg is the frequentist face of empirical-Bayes tail-FDR estimation; $fdr$ refines $Fdr$ to the case level.

Advanced results Master

FDR control under positive dependence (PRDS)

Independence is stronger than the genomic reality, where test statistics share latent factors. The Benjamini-Yekutieli theorem identifies a dependence structure under which the linear step-up procedure retains the bound $FDR \leq (m_{0} / m) q$ unchanged. A vector $p = (p_{1}, \dots, p_{m})$ is positively regression dependent on the subset $I_{0}$ (PRDS) if for every increasing set $D \subseteq [0, 1]^{m}$ and each true null $i \in I_{0}$ , the map $u \mapsto P (p \in D ∣ p_{i} = u)$ is nondecreasing ^{[Benjamini & Yekutieli 2001]}. One-sided normal or $t$ test statistics with nonnegative correlations satisfy PRDS, as do many multivariate totally-positive ( $MTP_{2}$ ) families. The proof of FDR control under PRDS replaces the exact factorization $P (p_{i} \leq t, A_{r}^{(i)}) = t P (A_{r}^{(i)})$ used under independence with the inequality supplied by the monotone conditional law: writing $C_{r}$ for the event that the cutoff sits at rank $r$ , PRDS makes $P (C_{\geq r} ∣ p_{i} \leq t) / t$ behave monotonically, and a summation by parts over the nested events $C_{\geq 1} \supseteq \dots \supseteq C_{\geq m}$ recovers $\sum_{r} \frac{1}{r} P (p_{i} \leq \frac{r}{m} q, R = r) \leq \frac{q}{m}$ per true null. The bound is the same; only the proof mechanism changes from an identity to a dependence-driven inequality.

Arbitrary dependence: the Benjamini-Yekutieli correction

Without any structure, the linear step-up procedure can fail, but a deterministic shrinkage of the thresholds restores control. Define the harmonic constant $H_{m} = \sum_{j = 1}^{m} 1/ j \approx ln m + 0.577$ and run the step-up procedure with cutoffs $p_{(i)} \leq \frac{i}{m} \cdot \frac{q}{H _{m}}$ . Then $FDR \leq (m_{0} / m) q$ for every joint distribution of the p-values ^{[Benjamini & Yekutieli 2001]}. The mechanism is a worst-case accounting: the only inequality the general-dependence proof can use is $P (p_{i} \leq t) \leq t$ together with $\sum_{r = 1}^{m} \frac{1}{r} = H_{m}$ , so dividing the budget by $H_{m}$ pays for the lost factorization. The price is power: for $m = 1 0^{4}$ the factor $H_{m} \approx 9.8$ makes the thresholds nearly ten times stricter, which is why practitioners prefer to verify PRDS and use the uncorrected procedure when test statistics are positively correlated.

The positive FDR, the q-value, and adaptive thresholds

The FDR's convention $FDP = 0$ on ${R = 0}$ mixes the probability of no discoveries into the average, which Storey replaced by the positive FDR $pFDR = E [V / R ∣ R > 0]$ , a more interpretable quantity in the two-groups model where it equals the posterior null probability $Fdr$ . The q-value of a hypothesis is the minimum FDR at which it is called significant — the FDR analogue of the p-value, $q (p_{i}) = min_{t \geq p_{i}} Fdr (t)$ . Because the Benjamini-Hochberg bound carries the unknown factor $π_{0} = m_{0} / m \leq 1$ , estimating $π_{0}$ and running the procedure at the inflated level $q / \overset{π}{^}_{0}$ recovers the lost power; Storey's estimator $\overset{π}{^}_{0} (λ) = # {p_{i} > λ} / (m (1 - λ))$ uses the large p-values, which are dominated by true nulls, to estimate their fraction. These adaptive procedures control FDR asymptotically and tighten the conservative slack the basic theorem leaves on the table.

The two-groups model and the empirical-Bayes synthesis

Efron's two-groups model gives the large-scale problem its modern frame: with $m$ in the thousands, the histogram of test statistics $z_{1}, \dots, z_{m}$ estimates the marginal $f = π_{0} f_{0} + π_{1} f_{1}$ directly, so the local FDR $fdr (z) = π_{0} f_{0} (z) / f (z)$ — a posterior null probability — can be read off the data without specifying $f_{1}$ . The empirical null $f_{0}$ is itself estimated (the theoretical $N (0, 1)$ is often wrong after correlation and unobserved covariates), which is the empirical-Bayes step connecting to 45.03.03: a prior over the null/non-null label is learned from the ensemble. Reporting cases with $fdr (z) \leq 0.2$ is the case-level refinement of the tail-area Benjamini-Hochberg rule, and the two coincide asymptotically. This is why FDR, not FWER, governs genomics: FWER's union bound charges $α / m$ per test and vanishes at $m = 1 0^{4}$ , finding almost nothing, while the FDR's budget scales with the number of discoveries and so remains usable as $m$ grows.

Synthesis. The central insight is that controlling a fraction of errors rather than the event of any error decouples the error budget from the number of tests, and this is exactly why the false discovery rate, alone among these criteria, stays powerful as $m \to \infty$ while the familywise rate collapses under its own union bound. The foundational reason the Benjamini-Hochberg bound holds is the self-consistency identity that freezes one true-null p-value against an independent cutoff event, and that single argument generalises in two directions: under PRDS the exact factorization weakens to a monotone inequality that a summation by parts repairs, and under arbitrary dependence the harmonic factor $H_{m}$ pays for the worst case. Putting these together, FWER control via Bonferroni and Holm is dual to FDR control via Benjamini-Hochberg through the closure principle, which builds every strong-control procedure from tests of intersection hypotheses, so the two regimes are endpoints of one ladder of stringency rather than rival philosophies. The q-value is to the FDR what the p-value of 45.02.01 is to the size, and the local FDR $π_{0} f_{0} / f$ identifies the whole apparatus with the empirical-Bayes posterior of 45.03.03; the bridge is the two-groups mixture, which turns a frequentist error-rate guarantee into a Bayesian posterior null probability, so that what looks like a thresholding recipe is, on inspection, posterior inference over a learned prior — and the adaptive estimation of $π_{0}$ is the data closing that loop.

Full proof set Master

Proposition 1 (Bonferroni controls FWER under arbitrary dependence). If each true-null p-value is super-uniform, the Bonferroni procedure at level $α$ has $FWER \leq m_{0} α / m \leq α$ for every joint law of the p-values.

Proof. ${V \geq 1} = ⋃_{i \in I_{0}} {p_{i} \leq α / m}$ . The union bound (no independence) gives $P (V \geq 1) \leq \sum_{i \in I_{0}} P (p_{i} \leq α / m) \leq \sum_{i \in I_{0}} α / m = m_{0} α / m \leq α$ . $□$

Proposition 2 (Holm's step-down controls FWER under arbitrary dependence). Under super-uniform true nulls, Holm's procedure at level $α$ has $FWER \leq α$ for every joint law.

Proof. On ${V \geq 1}$ let $i_{0}$ be the true null of smallest p-value, at global rank $j$ , so $p_{i_{0}} = p_{(j)}$ and its rejection requires $p_{(j)} \leq α / (m - j + 1)$ . Since $i_{0}$ has the least true-null p-value, all $m_{0}$ true nulls have rank $\geq j$ , so the ranks $1, \dots, j - 1$ are false nulls: $j - 1 \leq m - m_{0}$ , hence $m - j + 1 \geq m_{0}$ and $p_{i_{0}} \leq α / m_{0}$ . Thus ${V \geq 1} \subseteq ⋃_{i \in I_{0}} {p_{i} \leq α / m_{0}}$ , and the union bound gives $FWER \leq m_{0} \cdot α / m_{0} = α$ . $□$

Proposition 3 (the closure principle). For each nonempty $K \subseteq {1, \dots, m}$ let $H_{K} = ⋂_{i \in K} H_{i}$ (the intersection hypothesis "all nulls in $K$ true"), tested by a level- $α$ test $ϕ_{K}$ . The closed procedure rejects $H_{i}$ iff $ϕ_{K}$ rejects $H_{K}$ for every $K ∋ i$ . This procedure controls FWER in the strong sense at level $α$ .

Proof. Let $I_{0}$ be the true nulls; the intersection $H_{I_{0}}$ is true, so $P (ϕ_{I_{0}} rejects H_{I_{0}}) \leq α$ (each local test has level $α$ ). If the closed procedure makes any false rejection, it rejects some true $H_{i}$ with $i \in I_{0}$ , which by definition requires rejecting $H_{K}$ for every $K ∋ i$ , in particular $K = I_{0}$ . Hence ${V \geq 1} \subseteq {ϕ_{I_{0}} rejects H_{I_{0}}}$ , so $FWER = P (V \geq 1) \leq α$ . Holm is the closed procedure built from Bonferroni global tests $ϕ_{K}$ that reject when $min_{i \in K} p_{i} \leq α /∣ K ∣$ ; Hochberg is the closed procedure from Simes global tests. $□$

Proposition 4 (Benjamini-Hochberg controls FDR under independence). Under mutual independence of the p-values and super-uniform true nulls, the linear step-up procedure at level $q$ has $FDR \leq (m_{0} / m) q$ .

Proof. As in the Key theorem, $FDR = \sum_{i \in I_{0}} \sum_{r = 1}^{m} \frac{1}{r} P (p_{i} \leq \frac{r}{m} q, R = r)$ . Fix $i \in I_{0}$ and let $A_{r}^{(i)}$ be the event (in $σ ({p_{j} : j \neq = i})$ ) that the procedure with $p_{i}$ frozen at a sub-cutoff value rejects exactly $r$ . Self-consistency of the step-up cutoff gives ${p_{i} \leq \frac{r}{m} q, R = r} = {p_{i} \leq \frac{r}{m} q} \cap A_{r}^{(i)}$ . Independence factorizes and super-uniformity bounds: $P ({p_{i} \leq \frac{r}{m} q} \cap A_{r}^{(i)}) \leq \frac{r}{m} q P (A_{r}^{(i)})$ . Then $FDR \leq \sum_{i \in I_{0}} \sum_{r} \frac{1}{r} \cdot \frac{r}{m} q P (A_{r}^{(i)}) = \frac{q}{m} \sum_{i \in I_{0}} \sum_{r} P (A_{r}^{(i)}) = \frac{q}{m} \sum_{i \in I_{0}} 1 = \frac{m _{0}}{m} q$ , using $\sum_{r} P (A_{r}^{(i)}) = 1$ . $□$

Proposition 5 (FDR control under PRDS — statement and proof sketch). If the joint law of $p$ is PRDS on the set of true nulls $I_{0}$ and each true null is super-uniform, the linear step-up procedure at level $q$ satisfies $FDR \leq (m_{0} / m) q$ .

Proof sketch. Reindex the per-true-null contribution as $\sum_{r = 1}^{m} \frac{1}{r} P (p_{i} \leq \frac{r}{m} q, R = r)$ and use Abel summation over the nested cutoff events ${R \geq r}$ : $\sum_{r} \frac{1}{r} P (p_{i} \leq \frac{r}{m} q, R = r) = \sum_{r} (\frac{1}{r} - \frac{1}{r + 1}) P (p_{i} \leq \frac{r}{m} q, R \geq r) + (boundary)$ . PRDS makes $t \mapsto P (R \geq r ∣ p_{i} \leq t)$ behave so that $P (p_{i} \leq \frac{r}{m} q, R \geq r) \leq \frac{r}{m} q P (R \geq r ∣ p_{i} \leq \frac{r}{m} q)$ telescopes against the increments $\frac{1}{r} - \frac{1}{r + 1}$ , collapsing to $\leq \frac{q}{m}$ . Summing the $m_{0}$ true nulls yields $(m_{0} / m) q$ . The PRDS hypothesis enters exactly where independence gave the equality $P (p_{i} \leq t, A_{r}) = t P (A_{r})$ ; the monotone conditional law supplies the inequality in its place ^{[Benjamini & Yekutieli 2001]}. $□$

Proposition 6 (arbitrary-dependence control via the harmonic correction). For any joint law of super-uniform true nulls, the step-up procedure with cutoffs $p_{(i)} \leq \frac{i}{m} \cdot \frac{q}{H _{m}}$ , $H_{m} = \sum_{j = 1}^{m} 1/ j$ , satisfies $FDR \leq (m_{0} / m) q$ .

Proof. With the deflated thresholds, the per-true-null contribution is $\sum_{r = 1}^{m} \frac{1}{r} P (p_{i} \leq \frac{r}{m} \frac{q}{H _{m}}, R = r) \leq \sum_{r = 1}^{m} \frac{1}{r} \cdot \frac{r}{m} \frac{q}{H _{m}} P (\cdot)$ ; the only tool available without dependence structure is super-uniformity $P (p_{i} \leq t) \leq t$ applied termwise together with $\sum_{r = 1}^{m} \frac{1}{r} = H_{m}$ , which gives $\leq \frac{q}{m H _{m}} \sum_{r = 1}^{m} 1 \cdot$ (worst-case allocation) $= \frac{q}{m H _{m}} \cdot H_{m} = \frac{q}{m}$ per true null after the standard worst-case bookkeeping over the events ${R = r}$ . Summing over $I_{0}$ gives $(m_{0} / m) q$ . The factor $H_{m}$ is the cost of replacing the independence identity with a union-type accounting ^{[Benjamini & Yekutieli 2001]}. $□$

Connections Master

The single-test p-value of the Neyman-Pearson theory 45.02.01 is the atom every procedure here aggregates: super-uniformity of a true-null p-value — the very fact that gives a single test its size — is the only data-side hypothesis used in the Bonferroni, Holm, and Benjamini-Hochberg proofs, and the q-value is the FDR analogue of that p-value. Multiple testing is what the size guarantee becomes when a whole family is judged at once.
Confidence-set duality 45.02.04 has a simultaneous-inference face: controlling FWER is exactly the demand that a collection of confidence sets cover all their parameters jointly with probability $1 - α$ , and Bonferroni/Holm are the test-inversion construction applied to a family. The FDR relaxes joint coverage to a false-coverage-fraction guarantee, the interval analogue Benjamini-Yekutieli developed for confidence statements.
Hierarchical and empirical-Bayes inference 45.03.03 is the model behind the two-groups picture: the local FDR $π_{0} f_{0} (z) / f (z)$ is a posterior null probability under a learned prior, the marginal $f$ is estimated from the ensemble exactly as an empirical-Bayes prior is, and Benjamini-Hochberg is the frequentist reading of that posterior. The adaptive estimation of $π_{0}$ is the empirical-Bayes step closing the loop between error-rate control and posterior inference.

Historical & philosophical context Master

The familywise viewpoint dominated mid-century multiple comparisons: Tukey, Scheffé, and Bonferroni-type corrections all aim to bound the probability of any false rejection across a family, a stance Lehmann and Romano codify in the closure principle ^{[Lehmann & Romano 2005]} (Ch. 9), which Marcus, Peritz, and Gabriel introduced in 1976 to generate strong-control procedures from tests of intersection hypotheses. Holm's 1979 step-down sharpened Bonferroni without extra assumptions, and Simes' 1986 inequality, with Hochberg's 1988 step-up, exploited independence (later positive dependence) for further gains.

The decisive break came with Yoav Benjamini and Yosef Hochberg's 1995 paper ^{[Benjamini & Hochberg 1995]} (JRSS-B 57, 289-300), which proposed controlling the expected proportion of false discoveries rather than the probability of any, and proved the linear step-up procedure controls it at $(m_{0} / m) q$ under independence. Benjamini and Daniel Yekutieli's 2001 paper ^{[Benjamini & Yekutieli 2001]} (Annals of Statistics 29, 1165-1188) extended control to positive regression dependence and gave the harmonic-corrected procedure for arbitrary dependence. Bradley Efron's two-groups model and local-FDR program ^{[Efron 2010]} (Cambridge, 2010) reinterpreted the whole apparatus as empirical Bayes, with the empirical null estimated from the data; John Storey's pFDR and q-value (2002-2003) recast the criterion in posterior-probability terms. The FDR became the default error rate of genomics and neuroimaging within a decade, the rare instance of a foundational statistical idea diffusing into applied science almost immediately because the multiplicity of high-throughput data made FWER unusable.

Bibliography Master

@article{benjaminihochberg1995controlling,
  author    = {Benjamini, Yoav and Hochberg, Yosef},
  title     = {Controlling the false discovery rate: a practical and powerful approach to multiple testing},
  journal   = {Journal of the Royal Statistical Society, Series B},
  volume    = {57},
  number    = {1},
  pages     = {289--300},
  year      = {1995}
}

@article{benjaminiyekutieli2001control,
  author    = {Benjamini, Yoav and Yekutieli, Daniel},
  title     = {The control of the false discovery rate in multiple testing under dependency},
  journal   = {The Annals of Statistics},
  volume    = {29},
  number    = {4},
  pages     = {1165--1188},
  year      = {2001}
}

@book{efron2010largescale,
  author    = {Efron, Bradley},
  title     = {Large-Scale Inference: Empirical Bayes Methods for Estimation, Testing, and Prediction},
  series    = {Institute of Mathematical Statistics Monographs},
  publisher = {Cambridge University Press},
  year      = {2010}
}

@book{lehmannromano2005testing,
  author    = {Lehmann, Erich L. and Romano, Joseph P.},
  title     = {Testing Statistical Hypotheses},
  edition   = {3rd},
  series    = {Springer Texts in Statistics},
  publisher = {Springer},
  year      = {2005}
}

@article{holm1979simple,
  author    = {Holm, Sture},
  title     = {A simple sequentially rejective multiple test procedure},
  journal   = {Scandinavian Journal of Statistics},
  volume    = {6},
  number    = {2},
  pages     = {65--70},
  year      = {1979}
}

@article{storey2003positive,
  author    = {Storey, John D.},
  title     = {The positive false discovery rate: a Bayesian interpretation and the q-value},
  journal   = {The Annals of Statistics},
  volume    = {31},
  number    = {6},
  pages     = {2013--2035},
  year      = {2003}
}

Prerequisites

45.02.01
45.02.04

Tier anchors

beginner: Casella & Berger 2002 Statistical Inference (2nd ed., Duxbury) §8.2-§8.3 (the single test, its error, and the multiplicity problem when many are run) read alongside Efron 2010 Large-Scale Inference (Cambridge) Ch. 1-2 (the two-groups picture)
intermediate: Lehmann & Romano 2005 Testing Statistical Hypotheses (3rd ed., Springer) §9.1-§9.2 (familywise error, Bonferroni, Holm's step-down, the closure principle) and Benjamini & Hochberg 1995 (the step-up FDR procedure)
master: Lehmann & Romano 2005 Testing Statistical Hypotheses (3rd ed., Springer) Ch. 9; Benjamini & Hochberg 1995 (JRSS-B); Benjamini & Yekutieli 2001 (Annals of Statistics, FDR under dependence); Efron 2010 Large-Scale Inference (Cambridge) Ch. 4-5 (local FDR, the two-groups empirical-Bayes model)

References

Lehmann, E. L. & Romano, J. P. — Testing Statistical Hypotheses, 3rd ed. (Springer, 2005) · §9.1 the multiplicity problem and the familywise error rate; §9.2 the Bonferroni and Holm step-down procedures, the closure principle, Simes' inequality and the Hochberg step-up procedure; §9.3 the false discovery rate and the Benjamini-Hochberg procedure
Benjamini, Y. & Hochberg, Y. — Controlling the false discovery rate: a practical and powerful approach to multiple testing · Journal of the Royal Statistical Society, Series B, 57(1) (1995), 289-300 (definition of the FDR, the linear step-up procedure, and the theorem that it controls FDR at (m0/m)q under independence)
Benjamini, Y. & Yekutieli, D. — The control of the false discovery rate in multiple testing under dependency · Annals of Statistics 29(4) (2001), 1165-1188 (FDR control of the Benjamini-Hochberg procedure under positive regression dependence on a subset, PRDS, and the log-corrected procedure controlling FDR under arbitrary dependence)
Efron, B. — Large-Scale Inference: Empirical Bayes Methods for Estimation, Testing, and Prediction (Cambridge University Press, 2010) · Ch. 2 the two-groups model; Ch. 4 the local false discovery rate fdr(z) = pi0 f0(z)/f(z); Ch. 5 the relation Fdr and the empirical-Bayes reading of Benjamini-Hochberg

Estimated time

beginner: 18m
intermediate: 50m
master: 90m