The Reuters-21578 training set has 7,769 stories, 433 of them about grain, and 18,135 distinct terms after the text processing of Feature Selection. For each term we can test whether it appears more often in grain stories than chance would allow. At the 0.05 level, 1,071 terms pass. The Bonferroni correction of Multiple Comparisons and the Bonferroni Correction keeps 215. A classifier wants a few hundred candidate terms and can afford a few useless ones. It cannot afford a list in which a large share are noise. Nor does it gain much from a list so strict that it holds no false term at all. What error rate fits that situation, and which procedure controls it?
The false discovery rate fits it: the expected proportion of false discoveries among the hypotheses rejected. Benjamini and Hochberg (1995) defined it and gave a procedure that controls it, which on these data keeps 504 terms. This article is the unit's home of both. Later articles, q-Values and the Share of True Nulls in particular, build on the definitions and the theorem proved here.
Here is the route. First we count the errors a multiple test can make and define the false discovery rate, and prove how it relates to the family-wise error rate. Then we state the Benjamini–Hochberg procedure, its adjusted p-values and its reading as an estimate. Next comes the main theorem: under independence the procedure's false discovery rate is exactly the share of true nulls times the level, with Simes' test as a corollary. Then we treat dependence, proving a correction that works for any dependence and an example that shows it is needed. Finally we measure the procedure on simulated tests, on pairwise comparisons of NHANES age groups, and on the Reuters terms. The article assumes the course page above for the family-wise error rate, Holm's procedure and the union bound, and uses the unit's notation from Multiple Testing.
Counting the errors of many tests
Benjamini and Hochberg (1995, Table 1) set out the outcome of testing $m$ hypotheses in a two-by-two table. Of the $m$ hypotheses, $m_0$ are true and $m - m_0$ are not. A procedure rejects $R$ of them. Of the rejections, $V$ are true null hypotheses, the false discoveries, and $S = R - V$ are correct. Only $R$ is observed; $V$ and $S$ are not.
The false discovery proportion is the share of false discoveries among the rejections, $V/R$, set to 0 when nothing is rejected: $$Q = \frac{V}{\max(R, 1)}.$$ The false discovery rate is its expectation, $\mathrm{FDR} = E[Q]$. The family-wise error rate is $\mathrm{FWER} = P(V \ge 1)$, as on the course page.
Proposition 1 (Benjamini and Hochberg, 1995, §2.1). (a) If every null hypothesis is true, the false discovery rate equals the family-wise error rate. (b) In every case, $\mathrm{FDR} \le \mathrm{FWER}$.
Proof. (a) If $m_0 = m$, every rejection is false, so $V = R$. Then $Q = 1$ when $V \ge 1$ and $Q = 0$ when $V = 0$, so $Q$ is the indicator of $\{V \ge 1\}$ and its expectation is $P(V \ge 1)$. (b) In general $Q = 0$ when $V = 0$, and $Q = V/R \le 1$ when $V \ge 1$, since $V \le R$. So $Q$ is at most the indicator of $\{V \ge 1\}$, and taking expectations gives the inequality. $\blacksquare$
So any procedure that controls the family-wise error rate controls the false discovery rate, and a procedure that controls only the false discovery rate controls the family-wise error rate in the weak sense, when all nulls are true. The two rates differ most when many hypotheses are false: then $R$ is large, a single false discovery is a small fraction of it, and $Q$ is small while $V \ge 1$ is likely.
Example (why not the proportion among studies that reject something). A natural alternative is $E[V/R \mid R > 0]$, the expected proportion of false discoveries in the studies that report any. Benjamini and Hochberg (1995, §2.3) point out that no procedure can hold it below 1 when every null hypothesis is true: any rejection is then false, so $V/R = 1$ whenever $R > 0$. The false discovery rate is $P(R > 0)\,E[V/R \mid R > 0]$, and the factor $P(R > 0)$ is what makes it controllable. The conditional version returns, with an estimate of $\pi_0$, in q-Values and the Share of True Nulls.
The Benjamini–Hochberg procedure
Order the p-values $p_{(1)} \le \cdots \le p_{(m)}$ and compare the $i$-th smallest with $i\alpha/m$, a line through the origin with slope $\alpha/m$. Let $$k = \max\{i : p_{(i)} \le i\alpha/m\},$$ and reject $H_{(1)}, \ldots, H_{(k)}$; if no $i$ qualifies, reject nothing (Benjamini and Hochberg, 1995, §3.1). The procedure is step-up: it finds the largest $p_{(i)}$ under its line, and rejects that hypothesis and every one with a smaller p-value, even those above the line. Holm's procedure is step-down: it starts at the smallest p-value and stops at the first failure.
The first threshold, $\alpha/m$, is Bonferroni's, and the last, $\alpha$, is the unadjusted level. Hochberg's (1988) step-up procedure for the family-wise error rate uses $\alpha/(m - i + 1)$, which agrees at the two ends and is smaller in between; Benjamini and Hochberg (1995, §3.1) note that their procedure therefore rejects at least as much. Closed Testing proves that Hochberg's procedure controls the family-wise error rate under independence.
A tie-free statement of which hypotheses are rejected is useful in the proofs. For $c = 1, \ldots, m$ let $N(c)$ be the number of p-values at or below $c\alpha/m$.
Lemma 1. $k = \max\{c : N(c) \ge c\}$, and when $k \ge 1$ the rejected hypotheses are exactly those with $p_i \le k\alpha/m$.
Proof. $p_{(c)} \le c\alpha/m$ says that at least $c$ p-values are at or below $c\alpha/m$, that is, $N(c) \ge c$; so the two maxima are the same. Now let $k \ge 1$. Since $N(k) \ge k$, at least $k$ p-values are at or below $k\alpha/m$. If more were, say $N(k) = c' > k$, then $p_{(c')} \le k\alpha/m \le c'\alpha/m$, contradicting the maximality of $k$. So exactly $k$ p-values are at or below $k\alpha/m$, and they are the $k$ smallest, the ones rejected. $\blacksquare$
Adjusted p-values. The Benjamini–Hochberg adjusted p-value of $H_{(i)}$ is
$$\tilde p_{(i)} = \min_{j \ge i}\ \min\!\Big(1, \frac{m\,p_{(j)}}{j}\Big),$$
and the procedure at level $\alpha$ rejects $H_{(i)}$ exactly when $\tilde p_{(i)} \le \alpha$. Indeed, $\tilde p_{(i)} \le \alpha$ holds when some $j \ge i$ has $m p_{(j)}/j \le \alpha$, that is, $p_{(j)} \le j\alpha/m$ (for $\alpha < 1$ the cap at 1 changes nothing). Such a $j$ exists exactly when $k \ge i$. The minimum over $j \ge i$ makes the adjusted values non-decreasing down the ordering. This is the form that scipy.stats.false_discovery_control returns, as Statistical Inference in Python shows.
The procedure as an estimate. Benjamini and Hochberg (1995, §3.3, Theorem 2) give a second reading. Suppose every hypothesis is tested at a common level $t$, rejecting $R(t)$ of them. At most $m$ hypotheses are true nulls and each is rejected with probability at most $t$, so the expected number of false discoveries is at most $mt$, and $mt/R(t)$ is an estimate of the false discovery proportion that errs on the high side. The procedure tests at the largest $t$ whose estimate is at most $\alpha$. To see this, let $k$ be the procedure's number of rejections, with $k \ge 1$. For $t$ between $p_{(k)}$ and $p_{(k+1)}$ (or 1 if $k = m$), $R(t) = k$, because by Lemma 1 no other p-value ties with $p_{(k)}$; so the condition $mt/R(t) \le \alpha$ is $t \le k\alpha/m$. Since $p_{(k+1)} > (k+1)\alpha/m > k\alpha/m$, the condition holds up to $t^* = k\alpha/m$ and no further in that interval. For $t$ in a later interval, from $p_{(j)}$ to $p_{(j+1)}$ with $j > k$, it would need $t \le j\alpha/m < p_{(j)} \le t$, which is impossible. So the largest admissible threshold is $t^* = k\alpha/m$, and testing every hypothesis at $t^*$ rejects exactly $H_{(1)}, \ldots, H_{(k)}$. (Benjamini and Hochberg's Theorem 2 states the procedure as the choice of level that maximizes the number of rejections subject to this bound, and their proof considers only levels equal to the observed p-values, where the largest admissible one is $p_{(k)}$; it rejects the same set.) Replacing $m$ by an estimate of $m_0$ in this estimate is the idea that q-Values and the Share of True Nulls develops.
Why it controls the false discovery rate under independence
The theorem says more than control. Under independence, the procedure's false discovery rate is exactly $\pi_0\alpha$, whatever the false null hypotheses look like.
Here is the idea of the proof. Each true null hypothesis contributes $1/R$ to the false discovery proportion when it is rejected. If we knew $R$ in advance, the chance of rejecting a uniform p-value at threshold $R\alpha/m$ would be $R\alpha/m$, and $(R\alpha/m)/R = \alpha/m$; summing over the $m_0$ true nulls gives $m_0\alpha/m$. The proof makes this exact by computing $R$ from the other $m - 1$ p-values alone.
For a true null hypothesis $H_i$, let $R_i$ be the number of rejections the procedure makes when $p_i$ is replaced by 0 and the other p-values are kept. $R_i$ is a function of the other $m - 1$ p-values only, and $R_i \ge 1$, since the zero is always rejected.
Lemma 2. $H_i$ is rejected if and only if $p_i \le R_i\alpha/m$, and when it is rejected, $R = R_i$.
Proof. Write $N(c)$ for the counts of Lemma 1 with the original p-values and $N_i(c)$ for the counts with $p_i$ replaced by 0. Then $N_i(c) = N(c) + 1$ when $p_i > c\alpha/m$, and $N_i(c) = N(c)$ otherwise; so $N_i \ge N$, and by Lemma 1, $R_i \ge R$.
Suppose $p_i \le R_i\alpha/m$. Then $N(R_i) = N_i(R_i) \ge R_i$, so $R \ge R_i$ by Lemma 1, hence $R = R_i$, and $p_i \le R\alpha/m$, so $H_i$ is rejected by Lemma 1.
Conversely, suppose $H_i$ is rejected, so $R \ge 1$ and $p_i \le R\alpha/m$. Then $p_i \le c\alpha/m$ for every $c \ge R$, so $N_i(c) = N(c)$ for $c \ge R$. Since $R_i \ge R$, this gives $N(R_i) = N_i(R_i) \ge R_i$, so $R \ge R_i$, hence $R = R_i$ and $p_i \le R_i\alpha/m$. $\blacksquare$
Theorem 1 (Benjamini and Hochberg, 1995; equality: Benjamini and Yekutieli, 2001, Theorem 5.1). Suppose each true-null p-value $p_i$, $i \in \mathcal{I}_0$, is valid and independent of the vector of the other $m - 1$ p-values (jointly, not only of each one). Then the Benjamini–Hochberg procedure at level $\alpha$ has $$\mathrm{FDR} \le \frac{m_0}{m}\alpha = \pi_0\alpha,$$ with equality when every true-null p-value is uniform on $[0, 1]$.
Proof. By Lemma 2, a true null $H_i$ is rejected exactly when $p_i \le R_i\alpha/m$, and then $R = R_i$. So $$Q = \frac{V}{\max(R, 1)} = \sum_{i \in \mathcal{I}_0} \frac{\mathbf{1}\{p_i \le R_i\alpha/m\}}{R_i}.$$ Fix $i \in \mathcal{I}_0$ and condition on the other p-values, which fixes $R_i$. Since $p_i$ is independent of the vector of them and valid, $$E\Big[\frac{\mathbf{1}\{p_i \le R_i\alpha/m\}}{R_i}\ \Big|\ \text{the other p-values}\Big] = \frac{P(p_i \le c)\big|_{c = R_i\alpha/m}}{R_i} \le \frac{R_i\alpha/m}{R_i} = \frac{\alpha}{m},$$ with equality when $p_i$ is uniform, because then $P(p_i \le c) = c$ for $c \le 1$, and $R_i\alpha/m \le \alpha < 1$. Taking expectations and summing over the $m_0$ true nulls gives $E[Q] \le m_0\alpha/m$, with equality in the uniform case. $\blacksquare$
The theorem asks nothing of the false null hypotheses: their p-values may depend on one another in any way, as Benjamini and Hochberg (1995, §3.1) remark, and may have any distribution. The true-null p-values must each be independent of everything else. Benjamini and Hochberg proved the bound by induction on $m$, the number of hypotheses, with uniform p-values (their appendix). Benjamini and Yekutieli (2001, §5) gave a proof by conditioning and observed the equality for continuous statistics. Their proof also covers discrete test statistics, whose p-values are valid but not uniform. The argument above is of the same kind.
Corollary 1 (Simes' test). Suppose all $m$ null hypotheses are true and their p-values are jointly independent and uniform. Then $$P\big(p_{(i)} \le i\alpha/m \text{ for at least one } i\big) = \alpha,$$ and the probability is at most $\alpha$ for jointly independent valid p-values.
Proof. The event is $\{R \ge 1\}$ for the Benjamini–Hochberg procedure. With $m_0 = m$, Proposition 1(a) makes the false discovery rate equal to $P(R \ge 1)$, and Theorem 1 makes it $\alpha$, or at most $\alpha$ for valid p-values. $\blacksquare$
Rejecting the hypothesis that all $m$ nulls are true when some $p_{(i)} \le i\alpha/m$ is Simes' test of the intersection hypothesis; Benjamini and Yekutieli (2001, §2.3) report the equality as proved by Simes (1986) and, earlier, by Seeger (1968). Closed Testing uses it as a local test.
Checked by simulation. The script ran $m = 100$ one-sided $z$-tests, 2,000 replications for each of 30 seeds. True nulls had standard normal statistics, false nulls had mean 3, and the share of true nulls was 1, 0.9 or 0.5. With independent statistics the medians over the seeds of the false discovery proportion's average were
| $\pi_0$ | $\pi_0\alpha$ | BH: FDR | BH: mean $R$ | Holm: FDR | Holm: mean $R$ |
|---|---|---|---|---|---|
| 1 | 0.050 | 0.0520 (0.0481 to 0.0548) | 0.06 | 0.0505 | 0.05 |
| 0.9 | 0.045 | 0.0451 (0.0432 to 0.0468) | 6.48 | 0.0109 | 3.95 |
| 0.5 | 0.025 | 0.0249 (0.0246 to 0.0252) | 42.87 | 0.0015 | 20.53 |
with interquartile ranges over the seeds in parentheses. The Benjamini–Hochberg rate sits on $\pi_0\alpha$, as Theorem 1 says it must. With every null true, the exact rates are 0.05 for Benjamini–Hochberg and $1 - (1 - 0.05/100)^{100} = 0.0488$ for Holm's procedure, which then rejects something only when the smallest p-value is below $0.05/100$; the medians in the first row differ from these by simulation error, about 0.001 for a median of 30 seeds of 2,000. Holm's procedure, which controls the family-wise error rate, has a much lower false discovery rate and makes about half as many rejections when half the hypotheses are false. With $\pi_0 = 0.5$ the Benjamini–Hochberg procedure made at least one false discovery in 0.6580 of the replications; it was never meant to avoid that.
Dependence
The tests of a real study are rarely independent: the Reuters terms share their documents, and pairwise comparisons share their groups. What survives?
Positive dependence. Benjamini and Yekutieli (2001) proved that Theorem 1's bound $\pi_0\alpha$ still holds when the test statistics are positively regression dependent on each one from the set of true nulls (PRDS): for every true null $i$ and every increasing set $D$ of values of the statistics, $P(\text{statistics} \in D \mid \text{statistic } i = x)$ is nondecreasing in $x$ (their §1.3 and Theorem 1.2). Their §3.1 shows the condition holds for one-sided tests with jointly normal statistics in which each true-null statistic is nonnegatively correlated with every other. Their proof is longer than Theorem 1's and is not reproduced here. The script repeated the simulation with every pair of statistics correlated 0.5. The Benjamini–Hochberg rate was 0.0318, 0.0363 and 0.0233 for $\pi_0 = 1$, 0.9 and 0.5, each below $\pi_0\alpha$.
Arbitrary dependence. For dependence of any kind, a smaller level restores control. Write $L_m = 1 + 1/2 + \cdots + 1/m$.
Theorem 2 (Benjamini and Yekutieli, 2001, Theorem 1.3). If every true-null p-value is valid, the Benjamini–Hochberg procedure at level $\alpha/L_m$ has $\mathrm{FDR} \le \pi_0\alpha$, whatever the joint distribution of the p-values.
Proof. Write $c = \alpha/(mL_m)$, so the procedure's thresholds are $jc$, $j = 1, \ldots, m$. By Lemma 1, a true null $H_i$ is rejected when $p_i \le Rc$, so its contribution to $Q$ is $\mathbf{1}\{p_i \le Rc\}/R$, and $$E\Big[\frac{\mathbf{1}\{p_i \le Rc\}}{R}\Big] = \sum_{r=1}^{m}\frac{1}{r}P(R = r,\ p_i \le rc).$$ Cut $[0, mc]$ into the intervals $I_1 = [0, c]$ and $I_j = ((j-1)c, jc]$ for $j = 2, \ldots, m$, so that $\{p_i \le rc\}$ is the union of the disjoint events $\{p_i \in I_j\}$, $j \le r$. Then $$\sum_{r=1}^{m}\frac{1}{r}\sum_{j=1}^{r}P(R = r,\ p_i \in I_j) \le \sum_{r=1}^{m}\sum_{j=1}^{r}\frac{1}{j}P(R = r,\ p_i \in I_j) = \sum_{j=1}^{m}\frac{1}{j}P(R \ge j,\ p_i \in I_j) \le \sum_{j=1}^{m}\frac{1}{j}P(p_i \in I_j),$$ using $1/r \le 1/j$ for $j \le r$ and then exchanging the sums. Let $F(u) = P(p_i \le u)$, so $F(u) \le u$ by validity, and $P(p_i \in I_j) = F(jc) - F((j-1)c)$ for $j \ge 2$, $P(p_i \in I_1) = F(c)$. Summing by parts, $$\sum_{j=1}^{m}\frac{1}{j}P(p_i \in I_j) = \frac{F(mc)}{m} + \sum_{j=1}^{m-1}F(jc)\Big(\frac{1}{j} - \frac{1}{j+1}\Big) \le \frac{mc}{m} + \sum_{j=1}^{m-1}jc\,\frac{1}{j(j+1)} = c\Big(1 + \sum_{j=1}^{m-1}\frac{1}{j+1}\Big) = cL_m,$$ since each coefficient $1/j - 1/(j+1)$ is positive. That is $\alpha/m$. Summing over the $m_0$ true nulls gives $E[Q] \le m_0\alpha/m$. $\blacksquare$
The correction is costly. For $m = 15$, $L_{15} = 3.318$; for $m = 18{,}135$ terms it is about 10.4, so every threshold shrinks tenfold. Is it ever needed? The next example shows that, for two hypotheses, the uncorrected procedure can reach the bound $L_2\alpha = 1.5\alpha$ exactly, so no smaller correction works for every dependence.
Example (two hypotheses at one and a half times the level). Let both null hypotheses be true, write $a = \alpha/2$ with $\alpha < 2/3$, and let $U$ be uniform on $[0, 1]$. Set $p_1 = U$, and $p_2 = 1 - U$ when $U \le a$ or $U \ge 1 - a$, $p_2 = U$ otherwise. Both p-values are uniform: $p_2$ is $U$ with the two end pieces $[0, a]$ and $[1 - a, 1]$ exchanged by reflection. With $m = 2$, the Benjamini–Hochberg procedure rejects something when $\min(p_1, p_2) \le a$ or $\max(p_1, p_2) \le 2a = \alpha$. That happens in three disjoint ways: $U \le a$ (then $p_1 \le a$), $U \ge 1 - a$ (then $p_2 \le a$), and $a < U \le 2a$ (then both equal $U \le \alpha$). Each has probability $a$. In the remaining case, $2a < U < 1 - a$, both p-values equal $U > \alpha$. So $$\mathrm{FDR} = P(R \ge 1) = 3a = 1.5\,\alpha,$$ 0.075 at $\alpha = 0.05$. The construction moves the probability that independence spreads over the whole square into the three regions where a rejection happens, and keeps it out of the region where two p-values below $\alpha/2$ would share a single false discovery. The script's simulation of it (40,000 draws for each of 30 seeds) gave a median of 0.0754.
So positive dependence is harmless and dependence in general is not. Two cases matter in practice and fall between. For two-sided tests, Benjamini and Yekutieli (2001, §5) list as open how far control extends. For all pairwise comparisons of normal means they report that the statistics are not PRDS and that the question was open, though simulations had shown control. The next section measures that case on real data.
All pairwise comparisons of NHANES groups
How does the procedure behave on the pairwise comparisons of the course? To know which null hypotheses are true, the script built groups from two populations: the adults aged 18 to 29 in NHANES 2017–2018 (mean systolic pressure 113.18 mm Hg) and those aged 45 to 59 (127.56 mm Hg). Each sample had eight groups of 20, four drawn from each age band without replacement, and all 28 pairs were compared by Welch's $t$-test of The Welch t-Test. The 12 pairs within a band are true nulls, because their groups come from the same population, and the 16 pairs across bands are false, so $\pi_0 = 12/28$ and $\pi_0\alpha = 0.0214$. Over 1,000 samples for each of 30 seeds:
| Procedure | FDR | FWER | Mean rejections |
|---|---|---|---|
| Unadjusted, each at 0.05 | 0.0412 | 0.3585 | 13.93 |
| Holm | 0.0031 | 0.0210 | 5.77 |
| Benjamini–Yekutieli | 0.0045 | 0.0350 | 6.55 |
| Benjamini–Hochberg | 0.0199 (0.0188 to 0.0207) | 0.1765 | 11.35 |
The Benjamini–Hochberg procedure's false discovery rate stayed below $\pi_0\alpha$ in this design, as in the simulations Benjamini and Yekutieli cite, and it made almost twice as many rejections as Holm's. Its family-wise error rate was 0.1765: in about one sample in six it declared some within-band pair different, which is the price of the weaker guarantee. Even unadjusted tests have a low false discovery rate here, because the 16 real differences, about 14 mm Hg, are found so often that a false one is diluted; unadjusted tests give no such protection when most hypotheses are true.
Thousands of tests: the Reuters terms
Back to the grain stories. For a term that appears in $d$ of the $N = 7{,}769$ training stories, $N_{11}$ of them about grain, the null hypothesis is that the term is unrelated to the category. Fisher's exact test, a permutation test in which the labels are rearranged with the margins fixed, gives the one-sided p-value $$p = P(X \ge N_{11}), \qquad X \sim \text{Hypergeometric}(N = 7{,}769,\ 433 \text{ grain stories},\ d \text{ draws}),$$ as in Comparing Two Proportions. The one-sided version asks only whether the term is more common in grain stories, the direction a classifier for grain can use.
At $\alpha = 0.05$ over all 18,135 terms:
| Procedure | Terms rejected |
|---|---|
| Unadjusted | 1,071 |
| Bonferroni | 215 |
| Holm | 215 |
| Benjamini–Yekutieli | 333 |
| Benjamini–Hochberg | 504 |
The Benjamini–Hochberg cut-off is $504 \times 0.05/18{,}135 = 0.00139$, against Bonferroni's $0.05/18{,}135 = 2.8 \times 10^{-6}$. The top of the list is what a reader would expect, with wheat (227 of its 243 stories about grain), grain, agricultur, corn and tonn. Near the cut-off sit terms such as ireland and destroi, each in 5 grain stories out of 16, and impact, just outside. At level 0.10 the procedure keeps 645 terms.
A world in which every null is true. Permuting the grain labels among the stories keeps every margin and destroys every association, so after a permutation all 18,135 null hypotheses are true. The script drew 200 permutations for each of 30 seeds. The unadjusted tests rejected on average 170.79 terms per permutation (the median over the 30 seeds of each seed's average; interquartile range 168.41 to 172.58), far fewer than the $0.05 \times 18{,}135 = 907$ that uniform p-values would give. The Benjamini–Hochberg procedure rejected something in 29 of the 6,000 permutations, a share of 0.0048, and never more than 2 terms. (Per seed, the share of 200 permutations had median 0.0050 and interquartile range 0 to 0.0050; with so rare an event, the pooled count says more, and we report it.) Holm's procedure rejected something in 28, and the Benjamini–Yekutieli procedure in 2. In this world the false discovery rate equals the family-wise error rate (Proposition 1), so 0.0048 is the procedure's measured rate here, an order of magnitude below 0.05.
The low counts come from discreteness. A term in one story can reach at best $p = 433/7{,}769 = 0.0557$, so the 8,318 terms that occur in a single training story can never be rejected, even unadjusted; a term in two stories can reach 0.0031. Their p-values are valid, as Theorem 1 requires, but far from uniform, and the theorem's bound is then far from attained.
Filtering by document frequency. Terms in one or two stories cannot be rejected by the Benjamini–Hochberg procedure here: their smallest p-values, 0.0557 and 0.0031, are above its cut-off of 0.00139. Should such rare terms be removed before testing? They can be, without harming validity, because Fisher's test conditions on the margins. Removing terms by their document frequency $d$ selects tests by a quantity that does not involve the grain labels and that Fisher's test already treats as fixed, so each remaining p-value is still valid given the selection. Keeping the 5,061 terms that occur in at least five stories, the Benjamini–Hochberg procedure rejects 564 terms and Holm's 255. Holm's procedure loses nothing, since none of its 215 terms occurs in fewer than five stories. The Benjamini–Hochberg procedure loses the 54 discoveries it made among terms in three or four stories (a term in three stories, all about grain, has $p = 0.000172$, far below the cut-off), but gains more, because $m$ falls from 18,135 to 5,061 and every one of its thresholds rises by a factor of 3.6. The filter must use only the margins: filtering on $N_{11}$, the count in grain stories, would select on the test's outcome.
Do the discoveries hold up? The Reuters collection also has 3,019 test stories, 149 about grain, that played no part in the tests. The script repeated each term's test on them. Of Holm's 215 terms, 204 occur in the test stories, and 148 of these have a test-story p-value at most 0.05. Of the 289 terms that the Benjamini–Hochberg procedure adds to Holm's, 260 occur in the test stories and 89 reach 0.05 there. Of the 4,611 terms with at least five training stories that neither procedure rejected, 4,159 occur in the test stories and 176 reach 0.05. So the added discoveries are weaker evidence than Holm's, as their larger p-values say, and still several times as likely to recur as the terms left out. That is an observation on this split, not a measurement of the false discovery proportion: a term can be truly associated with grain and still fail to reach 0.05 in 149 stories.
What the false discovery rate does not promise
The guarantee is about an average over repetitions of the study. In any one study the false discovery proportion can be well above $\alpha$: Theorem 1 controls its expectation, not its spread, and when few hypotheses are rejected a single false one is a large share. Closed testing gives bounds that hold with probability at least $1 - \alpha$, simultaneously, on the number of false discoveries in any chosen set (Closed Testing, Theorem 9).
The rate is a property of the list, not of each entry. A term at the bottom of a Benjamini–Hochberg list is much more likely to be a false discovery than one at the top. The probability that a given hypothesis is null, given its p-value, is the local false discovery rate of the empirical Bayes reading, which q-Values and the Share of True Nulls takes up.
The family must be chosen before the data are seen. Splitting one family into several, each tested at $\alpha$, or merging families after the fact, changes what is rejected. Choosing the split after seeing the p-values is a selection of the kind Selective Inference and the Garden of Forking Paths examines.
What is proved here, what is cited, what the experiment shows
Proved here. The relation between the two error rates (Proposition 1). The characterization of the rejected set and the adjusted p-values (Lemma 1), and the procedure as the largest threshold whose estimated false discovery proportion is at most $\alpha$. The leave-one-out identity (Lemma 2) and the main theorem, $\mathrm{FDR} \le \pi_0\alpha$ under independence with equality for uniform null p-values (Theorem 1); Simes' equality (Corollary 1). The Benjamini–Yekutieli bound for any dependence (Theorem 2), here for valid rather than uniform null p-values, and the two-hypothesis example that attains it. The validity of filtering by margins for Fisher's test.
Cited. The definition, Table 1 and the procedure (Benjamini and Hochberg, 1995), whose original proof is by induction; the PRDS theorem and its normal case (Benjamini and Yekutieli, 2001, Theorem 1.2, §3.1); the open status of two-sided and pairwise comparisons as Benjamini and Yekutieli describe it; Hochberg's procedure and the history of Simes' test as reported there.
What the experiments show. The simulation table, which checks Theorem 1, and the positively correlated case, which agrees with the cited theorem. The NHANES design's error rates, which are observations for that design. The Reuters counts, the permutation world and the test-story recurrence, which describe these data.
Worked problems
The first problem uses the fifteen p-values of Benjamini and Hochberg's (1995, §3.2) example; the others are posed here on the course's NHANES sample and on the article's construction. The script checks every number.
Problem 1 (fifteen endpoints of a clinical trial). Benjamini and Hochberg (1995, §3.2) take the fifteen p-values of a family of comparisons from a trial of two thrombolytic treatments (Neuhaus et al., 1992): 0.0001, 0.0004, 0.0019, 0.0095, 0.0201, 0.0278, 0.0298, 0.0344, 0.0459, 0.3240, 0.4262, 0.5719, 0.6528, 0.7590 and 1.000. The fourth is the comparison of mortality. Apply the Bonferroni, Holm, Benjamini–Hochberg and Benjamini–Yekutieli procedures at 0.05, give the Benjamini–Hochberg adjusted p-values of the first nine, and say what changes at level 0.10.
Solution. Bonferroni, Holm and Benjamini–Yekutieli reject three hypotheses; Benjamini–Hochberg rejects four, including mortality.
Bonferroni's threshold is $0.05/15 = 0.0033$, and three p-values are below it. Holm's thresholds are $0.05/15$, $0.05/14$, $0.05/13$ and $0.05/12 = 0.00417$; the first three pass and the fourth, 0.0095, fails. For Benjamini–Hochberg, compare from the top: $p_{(9)} = 0.0459$ against $9 \times 0.05/15 = 0.030$ fails, and so do $p_{(8)}$ to $p_{(5)}$ (for example $0.0201 > 5 \times 0.05/15 = 0.0167$). Then $p_{(4)} = 0.0095 \le 4 \times 0.05/15 = 0.0133$, so $k = 4$, as Benjamini and Hochberg report. For Benjamini–Yekutieli, $L_{15} = 3.318$, and the thresholds are $i \times 0.05/(15 \times 3.318)$: $p_{(3)} = 0.0019 \le 0.00301$ and $p_{(4)} = 0.0095 > 0.00402$, and no later p-value passes, so $k = 3$.
The adjusted p-values $\tilde p_{(i)} = \min_{j \ge i} 15\,p_{(j)}/j$ are, for $i = 1$ to 9: 0.0015, 0.0030, 0.0095, 0.0356, 0.0603, 0.0639, 0.0639, 0.0645 and 0.0765. The fourth is below 0.05 and the fifth is not, which is the same decision. At level 0.10 all nine adjusted values are below 0.10, and the tenth, $15 \times 0.3240/10 = 0.486$, is not, so the procedure rejects nine.
Problem 2 (the four age groups). The course page compares four NHANES age groups in all six pairs, with p-values 0.0005 (60+ vs 18–29), 0.0025 (60+ vs 30–44), 0.0128 (60+ vs 45–59), 0.2348, 0.5288 and 0.5706. Apply the Benjamini–Hochberg procedure at 0.05 and give its adjusted p-values. What does the decision promise?
Solution. It rejects three: the oldest group differs from each of the others. Holm's procedure rejected two.
The thresholds are $i \times 0.05/6$: 0.0083, 0.0167, 0.025, 0.0333, 0.0417, 0.05. From the top, $0.5706 > 0.05$, $0.5288 > 0.0417$ and $0.2348 > 0.0333$, and $p_{(3)} = 0.0128 \le 0.025$, so $k = 3$. The adjusted p-values are $\min_{j \ge i} 6p_{(j)}/j$: 0.0030, 0.0074, 0.0256, 0.3522, 0.5706 and 0.5706 (from the unrounded p-values; the rounded 0.0025 would give 0.0075 for the second).
The promise is about the procedure, not this list: applied to studies like this one, the expected share of false differences among those declared is at most 0.05, if the six tests satisfy Theorem 1's conditions or the PRDS condition. Pairwise comparisons that share groups and a variance estimate satisfy neither, and the section on NHANES groups shows only that the rate stayed controlled in one simulated design. Holm's procedure, which Closed Testing improves for exactly this family, promises more: it is a procedure that, with probability at least 0.95, makes no false rejection at all.
Problem 3 (the construction, exactly). For two true null hypotheses, compute the Benjamini–Hochberg false discovery rate at $\alpha = 0.05$ when the p-values are independent and uniform, and for the construction of the dependence section.
Solution. It is 0.05 for independent p-values and 0.075 for the construction.
With both nulls true the false discovery rate is $P(R \ge 1)$, the probability that $\min(p_1, p_2) \le 0.025$ or $\max(p_1, p_2) \le 0.05$. For independent uniforms, $P(\min \le 0.025) = 1 - 0.975^2 = 0.049375$. The second event adds the square $(0.025, 0.05]^2$, of probability $0.025^2 = 0.000625$, which the first event does not cover. The sum is $0.05$ exactly, as Corollary 1 says. For the construction, the three disjoint pieces of $[0, 1]$ in which a rejection happens, $[0, 0.025]$, $(0.025, 0.05]$ and $[0.975, 1]$, have total length $0.075$. Dependence has removed the overlap that independence wastes: under independence, both p-values fall below 0.025 together with probability $0.025^2$, and that sample counts once though it has two small p-values; the construction never lets them fall there together.
Summary
- The false discovery rate is the expected share of false discoveries among the rejections. It equals the family-wise error rate when all nulls are true and is never larger.
- The Benjamini–Hochberg procedure rejects every hypothesis up to the largest $p_{(i)} \le i\alpha/m$. It is the largest common threshold whose estimated false discovery proportion is at most $\alpha$.
- Under independence its false discovery rate is exactly $\pi_0\alpha$ for uniform null p-values, by a leave-one-out argument; with every null true this is Simes' test.
- Under positive regression dependence the bound holds (cited). Under arbitrary dependence the level must be divided by $1 + 1/2 + \cdots + 1/m$, and two hypotheses can reach $1.5\alpha$ without it.
- On the Reuters terms for grain, the procedure keeps 504 terms where Holm's keeps 215; in a world of permuted labels it rarely rejects anything, because rare terms give conservative p-values; and its added discoveries recur in the test stories less often than Holm's but far more often than the terms left out.
What we have learned
When many hypotheses are false, controlling the chance of any false rejection discards most of the true ones, and controlling the expected share of false ones does not. The Benjamini–Hochberg procedure achieves that control with one line through the ordered p-values, and the proof shows why the line has slope $\alpha/m$: each true null contributes $\alpha/m$ to the rate whatever happens elsewhere.
The bound $\pi_0\alpha$ is below $\alpha$ by the factor $\pi_0$. When most hypotheses are false that waste is large, and estimating $\pi_0$ recovers it. q-Values and the Share of True Nulls estimates it and turns the procedure's adjusted p-values into Storey's q-values.
References
- Benjamini, Y., and Hochberg, Y. (1995). Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society, Series B, 57(1), 289–300. https://doi.org/10.1111/j.2517-6161.1995.tb02031.x record · 6 pages
- Benjamini, Y., and Yekutieli, D. (2001). The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4), 1165–1188. https://doi.org/10.1214/aos/1013699998 record
- Hochberg, Y. (1988). A sharper Bonferroni procedure for multiple tests of significance. Biometrika, 75(4), 800–802. https://doi.org/10.1093/biomet/75.4.800 record · 2 pages
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J) and Blood Pressure (BPX_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 95 pages
- Neuhaus, K. L., von Essen, R., Tebbe, U., Vogt, A., Roth, M., Riess, M., Niederer, W., Forycki, F., Wirtzfeld, A., Maeurer, W., Limbourg, P., Merx, W., and Haerten, K. (1992). Improved thrombolysis in acute myocardial infarction with front-loaded administration of alteplase: results of the rt-PA–APSAC patency study (TAPS). Journal of the American College of Cardiology, 19(5), 885–891. https://doi.org/10.1016/0735-1097(92)90265-O (Cited as Benjamini and Hochberg, 1995, report it.) record
- Seeger, P. (1968). A note on a method for the analysis of significances en masse. Technometrics, 10(3), 586–593. https://doi.org/10.1080/00401706.1968.10490605 (Cited as Benjamini and Yekutieli, 2001, report it.) record
- Simes, R. J. (1986). An improved Bonferroni procedure for multiple tests of significance. Biometrika, 73(3), 751–754. https://doi.org/10.1093/biomet/73.3.751 record · 2 pages