q-Values and the Share of True Nulls

What share of many tested hypotheses are true nulls, and what false discovery rate goes with declaring any one of them a discovery. The positive false discovery rate proved equal to the posterior probability of the null in the two-groups model, the q-value defined from it and shown to be a tail-area posterior probability, the local false discovery rate and the proof that the tail rate is its average, Storey's estimate of the share of true nulls proved conservative with its exact bias, its variance and its behavior under dependence, q-values proved equal to Benjamini–Hochberg adjusted p-values when the share is taken as one, and the adaptive procedure; all measured on two-sided Fisher tests of 878 Reuters terms against the category grain, on label permutations and on simulations with known truth. Worked problems on ten p-values by hand, the two-groups model, a weak alternative and the boundary term of the Reuters example.

The Reuters training collection has 7,769 stories, 433 of them about grain. For each of 878 stemmed terms, a two-sided Fisher exact test asks whether the term's occurrence is independent of the category, and the Benjamini–Hochberg procedure at level 0.05 declares 412 of the terms associated with grain. That answers one question: which terms can be declared so that, on average, no more than 5% of the declarations are false. It leaves two others open. How many of the 878 null hypotheses of independence are true at all? And for one particular term, what rate of false discoveries goes with declaring it? This article answers both: the share of true nulls is estimated from the p-values themselves, here as 0.346, an estimate that errs on the high side on average, and the error rate attached to a single term is its q-value.

The share of true nulls $\pi_0 = m_0/m$ is the fraction of the $m$ tested hypotheses that are true. The q-value of a test, introduced by Storey (2002, 2003), is the smallest positive false discovery rate at which that test would be declared a discovery. It is to the false discovery rate what the p-value is to the Type I error rate.

First we fix a threshold and ask what share of the discoveries it produces are false, which gives the positive false discovery rate. Then, in a model where each hypothesis is null by chance, we prove that this rate is a posterior probability, define the q-value and separate it from the local false discovery rate. Next we estimate $\pi_0$, prove the estimate conservative and measure its variance, and turn it into estimated q-values, which include the Benjamini–Hochberg procedure as a special case. Finally we read the whole construction as empirical Bayes inference. The article assumes The False Discovery Rate and the Benjamini–Hochberg Procedure, whose notation it follows, and the arithmetic of false findings in Type I and Type II Errors.

The grain terms

The data are the 7,769 training stories of the Reuters-21578 collection (ModApte split), with the text processing of Feature Selection: lowercase letters only, a short stop list, Porter stemming. A story is about grain when grain is among its categories; 433 are. For a term $t$, the stories form a $2 \times 2$ table by whether they contain $t$ and whether they are about grain, the table Feature Selection scores with mutual information and $\chi^2$. The null hypothesis $H_t$ is that occurrence of the term and membership in the category are independent.

Of the 18,135 distinct terms, 878 have all four expected counts (row total times column total over 7,769) at least 5. The article keeps those, so that each test has many possible outcomes and its p-values are close to continuous; the estimate of $\pi_0$ below depends on that. The False Discovery Rate and the Benjamini–Hochberg Procedure tests every term, one-sided, which suits its purpose but not this one. Each table is tested with the two-sided Fisher exact test, which conditions on both margins and so has an exact null distribution, the hypergeometric of Comparing Two Proportions.

Why not the chi-square test? With expected counts of 5 or more, Pearson's statistic is close to its $\chi^2_1$ limit near the 5% point, the region the usual rule of thumb protects. Multiple testing works far out in the tail, near $0.05/878 = 0.000057$, and there the approximation can be badly off. The script shows how. It permuted the grain labels across the stories 30 times (seeds 1 to 30), which makes every null hypothesis true while keeping every term's frequency, and ran the Benjamini–Hochberg procedure on both kinds of p-value. On the chi-square p-values it declared at least one term in 6 of the 30 permutations, with up to 8 declarations; on the Fisher p-values, in 1. In one permutation the term good had chi-square p-value $4.2 \times 10^{-6}$ and Fisher p-value $4.1 \times 10^{-5}$, a factor of ten. A p-value that is accurate at 0.05 need not be accurate at 0.00005.

Of the 878 Fisher p-values, 466 are at most 0.05. The histogram in the figure below shows their shape: a tall bar at the left, from terms strongly associated with grain (wheat is in 227 of the 243 stories that contain it), and a low, roughly flat floor across the rest. That floor is what the rest of the article reads.

Histograms of the 878 two-sided Fisher p-values of the grain terms (left) and of the same tests after one random permutation of the grain labels (right), in 20 bins of width 0.05. The vertical axis is on a log scale. Notice that the floor of the left histogram, beyond 0.5, sits at about a third of the count a uniform distribution of all 878 p-values would give per bin (dotted line), and that the dashed line at Storey's estimate, 0.346, tracks it. With permuted labels every null is true and the bars hover around the dotted line, except the last, which collects the p-values of exactly 1 that a discrete test produces.
Histograms of the 878 two-sided Fisher p-values of the grain terms (left) and of the same tests after one random permutation of the grain labels (right), in 20 bins of width 0.05. The vertical axis is on a log scale. Notice that the floor of the left histogram, beyond 0.5, sits at about a third of the count a uniform distribution of all 878 p-values would give per bin (dotted line), and that the dashed line at Storey's estimate, 0.346, tracks it. With permuted labels every null is true and the bars hover around the dotted line, except the last, which collects the p-values of exactly 1 that a discrete test produces.

Two error rates for a fixed threshold

Suppose every hypothesis with a p-value at most a fixed threshold $t$ is declared a discovery. Write $R(t)$ for the number of discoveries and $V(t)$ for the number of them that are true nulls. The false discovery proportion is $V(t)/\max(R(t), 1)$, and its expectation is the false discovery rate,

$$\mathrm{FDR}(t) = E\!\left[\frac{V(t)}{\max(R(t), 1)}\right].$$

Storey (2003, Section 2) recalls that Benjamini and Hochberg (1995) considered several ways of handling the case $R = 0$ and chose this one. He proposes another, the positive false discovery rate,

$$\mathrm{pFDR}(t) = E\!\left[\frac{V(t)}{R(t)} \,\middle|\, R(t) > 0\right],$$

the expected share of false discoveries given that there is at least one discovery.

Lemma 1. $\mathrm{FDR}(t) = \mathrm{pFDR}(t)\,P(R(t) > 0)$.

Proof. On the event $R(t) = 0$ the ratio $V(t)/\max(R(t), 1)$ is 0, and on $R(t) > 0$ it equals $V(t)/R(t)$. So $E[V/\max(R, 1)] = E[V/R \mid R > 0]\,P(R > 0) + 0 \cdot P(R = 0)$. $\blacksquare$

The two rates differ when a discovery is unlikely. If every null hypothesis is true, every discovery is false, so $V/R = 1$ whenever $R > 0$ and $\mathrm{pFDR}(t) = 1$ for every $t$. No procedure can hold $\mathrm{pFDR}$ below a level $\alpha < 1$ whatever the truth, which is why Benjamini and Hochberg built their procedure around the FDR. Storey (2002) turned the question around. His abstract states the plan: instead of fixing the error rate and estimating a rejection region, "we fix the rejection region and then estimate its corresponding error rate". With the region fixed, both rates can be estimated, and the pFDR has a cleaner meaning, which the next section proves.

The two-groups model

Here is the idea. If each hypothesis is null by a coin flip with probability $\pi_0$, and the tests are independent, then each discovery is an independent draw from the same population of "p-values at most $t$", and the expected share of nulls among discoveries is simply the share of nulls in that population. Bayes' theorem gives that share.

The model. The pairs $(H_1, p_1), \dots, (H_m, p_m)$ are independent and identically distributed. $H_i = 0$ with probability $\pi_0$ (the null is true) and $H_i = 1$ with probability $1 - \pi_0$. Given $H_i = 0$ the p-value is uniform on $[0, 1]$; given $H_i = 1$ it has a distribution function $F_1$. The p-values then have the mixture distribution

$$F(t) = P(p_i \le t) = \pi_0 t + (1 - \pi_0)F_1(t).$$

Efron and Hastie (2016, eq. 15.19) call this the two-groups model and write it for z-values; it is the model of Storey (2002, Theorem 1) and Storey (2003, Theorem 1).

Theorem 1 (Storey, 2003, Theorem 1). In the two-groups model, for every $t$ with $F(t) > 0$ and every $m$,

$$\mathrm{pFDR}(t) = \frac{\pi_0 t}{F(t)} = P(H_i = 0 \mid p_i \le t).$$

Proof. The second equality is Bayes' theorem: $P(H_i = 0, p_i \le t) = \pi_0 t$ and $P(p_i \le t) = F(t)$.

For the first, fix a set $S$ of $k \ge 1$ indices and let $A_S$ be the event that $p_i \le t$ exactly for $i \in S$. On $A_S$, $R = k$ and $V = \sum_{i \in S} \mathbf{1}\{H_i = 0\}$. The event $A_S$ is the intersection of the events $\{p_i \le t\}$ for $i \in S$ and $\{p_i > t\}$ for $i \notin S$, one event per index. The pairs are independent, so conditioning on $A_S$ changes the distribution of $H_i$ only through the event about its own p-value: for $i \in S$, $P(H_i = 0 \mid A_S) = P(H_i = 0 \mid p_i \le t)$. Hence

$$E[V \mid A_S] = k\,P(H = 0 \mid p \le t), \qquad E\!\left[\frac{V}{R} \,\middle|\, A_S\right] = P(H = 0 \mid p \le t).$$

The events $A_S$ for all nonempty $S$ partition the event $R > 0$, and the conditional expectation is the same on each, so it is also the expectation given $R > 0$. $\blacksquare$

The rate does not depend on $m$. It is also the ratio of expectations, $E[V(t)]/E[R(t)] = m\pi_0 t/(mF(t))$, which Storey (2003, Corollary 1) notes. Two remarks keep the theorem in its place:

  • The hypotheses must be random. If $m_0$ is a fixed number, the indicators $H_i$ are not independent (they must add up to $m - m_0$), and the theorem no longer holds exactly. Storey (2003, Section 5, Theorem 4) gives convergence conditions, met under some forms of dependence, under which an analogous result holds as $m \to \infty$.
  • Valid instead of uniform. If the null p-values are only valid, $P(p_i \le t \mid H_i = 0) \le t$, the same argument gives $\mathrm{pFDR}(t) \le \pi_0 t/F(t)$ with $F$ computed from the actual null distribution.

Example (one in three). Let $\pi_0 = 0.9$ and let each test be a one-sided $z$ test whose statistic is $N(0, 1)$ under the null and $N(3, 1)$ under the alternative. The threshold $t = 0.05$ corresponds to $z \ge 1.645$, so the power is $F_1(0.05) = \Phi(3 - 1.645) = 0.912$ and $F(0.05) = 0.9(0.05) + 0.1(0.912) = 0.136$. Then

$$\mathrm{pFDR}(0.05) = \frac{0.9 \times 0.05}{0.136} = 0.330.$$

Every test has level 0.05 and power 0.91, yet a third of the discoveries are false, because nine hypotheses in ten are null. This is the calculation of the table of false findings in Type I and Type II Errors, now with a theorem saying that it holds exactly for the expected share of false discoveries in one study of any size, given that it makes at least one, not only as a long-run fraction over a field of studies.

The q-value

A p-value is the smallest level at which a test would reject. Storey (2002, Definition 3) defines the q-value the same way with the pFDR in place of the level: for an observed p-value $p$, rejecting it means using some threshold $t \ge p$, so

$$q(p) = \inf_{t \ge p}\, \mathrm{pFDR}(t) = \inf_{t \ge p}\, \frac{\pi_0 t}{F(t)}.$$

The infimum is there because $\mathrm{pFDR}(t)$ need not increase with $t$: a larger region can contain proportionally more alternatives. Under a condition met by most tests, it does increase, and then the q-value has a direct meaning.

Theorem 2. If $F_1(t)/t$ does not increase on $(0, 1]$, then $\mathrm{pFDR}(t)$ does not decrease, and

$$q(p) = \mathrm{pFDR}(p) = P(H = 0 \mid p_i \le p).$$

The condition holds whenever $F_1$ is concave, and $F_1$ is concave for the one-sided $z$ test against a normal alternative with mean $\mu > 0$.

Proof. Dividing by $t$, $\mathrm{pFDR}(t) = \pi_0/[\pi_0 + (1 - \pi_0)F_1(t)/t]$, which does not decrease when $F_1(t)/t$ does not increase. Then the infimum over $t \ge p$ is attained at $t = p$.

If $F_1$ is concave with $F_1(0) = 0$, take $0 < s < t$ and write $s = (s/t)\,t + (1 - s/t)\cdot 0$. Concavity gives $F_1(s) \ge (s/t)F_1(t) + (1 - s/t)F_1(0) = (s/t)F_1(t)$, that is, $F_1(s)/s \ge F_1(t)/t$.

For the one-sided $z$ test, a p-value $t$ corresponds to the critical value $u = \Phi^{-1}(1 - t)$, and $F_1(t) = P(Z + \mu \ge u) = \Phi(\mu - u)$. Since $du/dt = -1/\phi(u)$,

$$F_1'(t) = \frac{\phi(\mu - u)}{\phi(u)} = e^{\mu u - \mu^2/2}.$$

As $t$ increases, $u$ decreases, so for $\mu > 0$ the derivative decreases and $F_1$ is concave. $\blacksquare$

Storey (2003, Proposition 1 and Theorem 2) states the same condition. The q-value is then a posterior probability, but of a specific event: that the hypothesis is null given that its p-value is at most the observed one. In the example, the q-value of $p = 0.05$ is 0.330 and that of $p = 0.001$ is $0.9(0.001)/F(0.001) = 0.0009/0.0473 = 0.0190$.

Example (a q-value is not the probability that this hypothesis is null). A common reading of "$q = 0.33$" is "this hypothesis has a one-in-three chance of being null". It is not. The q-value averages over every p-value below the observed one, most of them much smaller. The probability given the observed value itself is the local false discovery rate of Efron and colleagues, written with the z-value $z$ and the densities $f_0$, $f_1$ and $f = \pi_0 f_0 + (1 - \pi_0)f_1$ (Efron and Hastie, 2016, eq. 15.38):

$$\mathrm{fdr}(z) = P(H = 0 \mid Z = z) = \frac{\pi_0 f_0(z)}{f(z)}.$$

In the example, at the boundary $z = 1.645$ it is

$$\mathrm{fdr}(1.645) = \frac{0.9\,\phi(1.645)}{0.9\,\phi(1.645) + 0.1\,\phi(1.645 - 3)} = 0.854.$$

A test that just reaches $p = 0.05$ is null with probability 0.854, not 0.330. At $p = 0.001$ ($z = 3.090$) the two numbers are 0.071 and 0.0190.

Theorem 3 (the tail rate is an average of the local rate). In the two-groups model, with rejection for $z \ge z_0$ and $S_0$, $S$ the null and mixture probabilities of $[z_0, \infty)$,

$$\mathrm{pFDR} = \frac{\pi_0 S_0(z_0)}{S(z_0)} = E[\mathrm{fdr}(Z) \mid Z \ge z_0].$$

Proof. $E[\mathrm{fdr}(Z) \mid Z \ge z_0] = \int_{z_0}^\infty \frac{\pi_0 f_0(z)}{f(z)}\,f(z)\,dz \big/ S(z_0) = \pi_0\int_{z_0}^\infty f_0(z)\,dz \big/ S(z_0) = \pi_0 S_0(z_0)/S(z_0)$, which is Theorem 1 in terms of $z$. $\blacksquare$

Efron and Hastie (2016, eq. 15.44 and note 4 of Section 15.7) give the same identity. When $\mathrm{fdr}$ decreases into the tail, as it does in the example, its average over the region is smaller than its value at the region's edge. So the hypotheses just inside a q-value cutoff are null more often than the cutoff says, and those deep inside less often. The script checks Theorem 3 on the example by numerical integration.

One more distinction. Storey (2003, Section 4, Remark) points out that a q-value is not an adjusted p-value in Shaffer's sense, since an adjusted p-value is defined through a procedure that controls an error rate at every level, and no procedure controls the pFDR.

Estimating the share of true nulls

Theorem 1 needs $\pi_0$, which is unknown. Here is the idea for estimating it. Null p-values are uniform, so they spread evenly over $[0, 1]$. Alternative p-values crowd toward 0. Far from 0, say above $\lambda = 0.5$, nearly all p-values come from nulls, and the nulls supply $m_0(1 - \lambda)$ of them on average. Counting the p-values above $\lambda$ and dividing by $m(1 - \lambda)$ estimates $\pi_0$. Schweder and Spjøtvoll (1982) proposed reading the number of true hypotheses from a plot of the cumulative p-values, where the nulls form a straight line. Storey (2002, eq. 6) gives the estimate in the form used here:

$$\hat\pi_0(\lambda) = \frac{W(\lambda)}{m(1 - \lambda)}, \qquad W(\lambda) = \#\{i : p_i > \lambda\}.$$

Theorem 4 (the estimate is conservative). Suppose the p-values of the true nulls are valid. Then, whatever the dependence among the tests, for fixed hypotheses with $m_0$ true nulls,

$$E[\hat\pi_0(\lambda)] = \pi_0 + \frac{1}{m(1 - \lambda)}\Big[\sum_{i \in \mathcal{I}_0}\big(P(p_i > \lambda) - (1 - \lambda)\big) + \sum_{i \notin \mathcal{I}_0} P(p_i > \lambda)\Big] \ \ge\ \pi_0.$$

In the two-groups model with uniform null p-values, $E[\hat\pi_0(\lambda)] = \pi_0 + (1 - \pi_0)\dfrac{1 - F_1(\lambda)}{1 - \lambda}$. If the tests are also independent, $W(\lambda)$ is binomial with $m$ trials and success probability $1 - F(\lambda)$, so

$$\operatorname{Var}[\hat\pi_0(\lambda)] = \frac{F(\lambda)\,[1 - F(\lambda)]}{m(1 - \lambda)^2}.$$

Proof. $W(\lambda) = \sum_i \mathbf{1}\{p_i > \lambda\}$, and the expectation of a sum is the sum of the expectations, whether or not the terms are dependent. So $E[W(\lambda)] = \sum_{i \in \mathcal{I}_0} P(p_i > \lambda) + \sum_{i \notin \mathcal{I}_0} P(p_i > \lambda)$. Adding and subtracting $m_0(1 - \lambda)$ and dividing by $m(1 - \lambda)$ gives the displayed formula, with $m_0(1-\lambda)/(m(1-\lambda)) = \pi_0$. Validity gives $P(p_i > \lambda) = 1 - P(p_i \le \lambda) \ge 1 - \lambda$ for each true null, so the first sum is nonnegative; the second is a sum of probabilities. In the two-groups model each p-value exceeds $\lambda$ with probability $\pi_0(1 - \lambda) + (1 - \pi_0)(1 - F_1(\lambda)) = 1 - F(\lambda)$, so $E[W] = m(1 - F(\lambda))$, which rearranges to the stated bias. Under independence the indicators are independent with that probability, so $W$ is binomial and $\operatorname{Var}(W) = mF(\lambda)(1 - F(\lambda))$; divide by $m^2(1 - \lambda)^2$. $\blacksquare$

The bias has two sources, each visible in the formula, and one thing that might be expected to contribute does not:

  • Alternatives above $\lambda$. Weak alternatives leave p-values spread across $[0, 1]$, and those above $\lambda$ are counted as nulls. In the example ($\mu = 3$), $F_1(0.5) = \Phi(3) = 0.99865$, and $E[\hat\pi_0(0.5)] = 0.9 + 0.1(0.00135)/0.5 = 0.90027$, almost no bias. With $\mu = 1$ instead it is 0.9317 (Worked problem 3).
  • Discrete tests. A valid test with few possible outcomes has $P(p > \lambda) > 1 - \lambda$ under the null; a p-value of exactly 1 is common. Every such null adds to the first sum.
  • Not dependence. Dependence leaves the expectation alone and changes only the variance, which is the subject of the section on permutations.

Storey, Taylor and Siegmund (2004, Section 2.1) describe the choice of $\lambda$ as a bias–variance trade-off: a smaller $\lambda$ counts more p-values, so the estimate varies less, but more of the counted p-values come from alternatives. Storey (2002, Section 9) chooses $\lambda$ by a bootstrap estimate of mean squared error over the grid $0, 0.05, \dots, 0.95$. This article uses $\lambda = 1/2$ throughout, the value Storey, Taylor and Siegmund (2004, Table 2) use in their numerical study.

The grain terms. Of the 878 p-values, $W(0.5) = 152$ exceed one half, so

$$\hat\pi_0(0.5) = \frac{152}{878 \times 0.5} = 0.346.$$

Other choices of $\lambda$ give similar values:

$\lambda$ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
$\hat\pi_0(\lambda)$ 0.433 0.390 0.371 0.363 0.346 0.350 0.342 0.382 0.353

By Theorem 4 the expectation of each entry is at least the true share, so the data say that at most about a third of the terms are independent of the category, in the averaged sense of an expectation. The estimate is low, and it is worth asking why.

Example (why so few terms are independent of grain). A reader may expect most words to have nothing to do with grain, so that $\pi_0$ would be close to 1. Exact independence is a strong claim, and with 7,769 stories small departures from it are detectable. Two sources are visible in the data:

  • Story length. A grain story contains a median of 55 distinct stemmed terms, against 37 for other stories, so almost any common term is more likely to appear in a grain story. Of the 412 terms the Benjamini–Hochberg procedure declares, 67% occur more often in grain stories than independence predicts. Testing within five strata of story length (quintiles, with the Mantel–Haenszel test in its normal form) largely removes this source, and $\hat\pi_0(0.5)$ rises only to 0.390.
  • Topic. Grain stories share a vocabulary of trade, governments and quantities that other categories use less.

The null hypothesis of exact independence is false for most of these terms, and Storey's estimate says so. Whether a term "matters" is a different question, about the size of its association, which a share of true nulls cannot answer. Efron and Hastie (2016, Section 15.5, "Effect size considerations") make the general point: the testing setup, in which a large fraction of the cases are null, may be the wrong model, and one with a continuous distribution of effect sizes may fit better.

Estimated false discovery rates and q-values

With $\pi_0$ estimated, Theorem 1 suggests an estimate of the false discovery rate of a fixed threshold. Replace $\pi_0$ by $\hat\pi_0(\lambda)$ and $F(t)$ by the share of p-values at most $t$:

$$\widehat{\mathrm{FDR}}_\lambda(t) = \frac{\hat\pi_0(\lambda)\,m\,t}{\max(R(t), 1)}.$$

This is Storey's (2002, eq. 10) estimate, also eq. 3 of Storey, Taylor and Siegmund (2004). The numerator is the expected number of null p-values below $t$, and the denominator the number of discoveries. Storey (2002) also gives a version for the pFDR with an extra factor $1/[1 - (1 - t)^m]$, which matters only for very small $t$; this article uses the FDR version. The estimated q-values are computed in the manner of Storey's (2002) Algorithm 2, with this estimate in place of his pFDR version: order the p-values, and set

$$\hat q_{(i)} = \min\Big(\min_{k \ge i}\ \frac{\hat\pi_0\,m\,p_{(k)}}{k},\ 1\Big),$$

the smallest estimated rate over thresholds that reject the $i$-th smallest p-value. Taking the minimum over $k \ge i$ makes the q-values increase with the p-values.

Theorem 5 (q-values and the Benjamini–Hochberg procedure). (a) With $\hat\pi_0 = 1$, the estimated q-values are the Benjamini–Hochberg adjusted p-values $\tilde p_i$, and declaring every hypothesis with $\hat q_i \le \alpha$ is the Benjamini–Hochberg procedure at level $\alpha$. (b) With any value $\hat\pi_0 > 0$, declaring every hypothesis with $\hat q_i \le \alpha$ is the Benjamini–Hochberg procedure at level $\alpha$ with $m$ replaced by $\hat\pi_0 m$.

Proof. (a) With $\hat\pi_0 = 1$ the formula is $\min_{k \ge i}\, m p_{(k)}/k$, capped at 1, which is the definition of the adjusted p-value in The False Discovery Rate and the Benjamini–Hochberg Procedure; that article proves that $\tilde p_{(i)} \le \alpha$ exactly when the procedure rejects $H_{(i)}$. (b) $\hat q_{(i)} \le \alpha$ holds exactly when some $k \ge i$ has $\hat\pi_0 m p_{(k)}/k \le \alpha$, that is, $p_{(k)} \le k\alpha/(\hat\pi_0 m)$ (for $\alpha < 1$ the cap at 1 changes nothing). The largest such $k$, call it $\hat k$, exists if any does, and the hypotheses with $\hat q \le \alpha$ are then $H_{(1)}, \dots, H_{(\hat k)}$: every $i \le \hat k$ has $k = \hat k$ available, and no $i > \hat k$ has any. That is the step-up rule with $m$ replaced by $\hat\pi_0 m$. $\blacksquare$

Storey, Taylor and Siegmund (2004, Lemmas 1 and 2) state both parts in the language of thresholds. Part (b) explains what the estimate of $\pi_0$ buys. The False Discovery Rate and the Benjamini–Hochberg Procedure proves that, for independent tests with uniform null p-values, the procedure's FDR is exactly $\pi_0\alpha$, below the target by the factor $\pi_0$. Replacing $m$ by $\pi_0 m$ would make it exactly $\alpha$; replacing it by an estimate of $\pi_0 m$ tries to.

What is guaranteed. Three results, of different strength:

  • Conservative point estimate. For a fixed threshold $t$ and independent, uniform null p-values, $E[\widehat{\mathrm{FDR}}_\lambda(t)] \ge \mathrm{FDR}(t)$ (Storey, Taylor and Siegmund, 2004, Theorem 1; cited, not proved here).
  • Conservative in the limit. In the two-groups model, as $m \to \infty$ with $t$ and $\lambda$ fixed, $$\widehat{\mathrm{FDR}}_\lambda(t) \to \Big[\pi_0 + (1 - \pi_0)\frac{1 - F_1(\lambda)}{1 - \lambda}\Big]\frac{t}{F(t)} \ \ge\ \mathrm{pFDR}(t) \quad \text{almost surely.}$$ Proof. $W(\lambda)/m$ and $R(t)/m$ are averages of independent, identically distributed indicators with means $1 - F(\lambda)$ and $F(t)$, so by the strong law of large numbers (The Laws of Large Numbers) they converge almost surely to those means. Then $\hat\pi_0(\lambda) \to (1 - F(\lambda))/(1 - \lambda)$, which equals the bracket by the computation in Theorem 4, and $m t/\max(R(t), 1) \to t/F(t)$ since $F(t) > 0$. The bracket is at least $\pi_0$, and $\pi_0 t/F(t) = \mathrm{pFDR}(t)$ by Theorem 1. $\blacksquare$ Storey (2002, Theorem 4) states the same limit for his pFDR estimate, which differs from this one by the factor $1/[1 - (1 - t)^m]$, which tends to 1.
  • Control by the adaptive procedure. The Benjamini–Hochberg procedure with $m$ replaced by $\hat\pi_0^*(\lambda)\,m$, where $\hat\pi_0^*(\lambda) = (W(\lambda) + 1)/(m(1 - \lambda))$, and with no p-value above $\lambda$ rejected, has $\mathrm{FDR} \le (1 - \lambda^{m_0})\alpha$ when the null p-values are independent (Storey, Taylor and Siegmund, 2004, Theorem 3, proved there with a martingale argument; cited, not proved here). The added 1 and the restriction to $p \le \lambda$ are the price of a finite-sample guarantee. Benjamini, Krieger and Yekutieli (2006) prove control for a two-stage procedure that estimates $m_0$ with a first pass of the Benjamini–Hochberg procedure.

The simulation. The script checked these statements in the example model ($m = 1{,}000$, $\pi_0 = 0.9$, alternatives $N(3, 1)$, one-sided p-values; the hypotheses drawn at random as in Theorem 1), with 30 seeds of 200 sets each. With independent tests the median false discovery rate over the seeds was 0.0449 for the Benjamini–Hochberg procedure (interquartile range 0.0437 to 0.0459), as $\pi_0\alpha = 0.045$ requires, and 0.0502 for the adaptive procedure (0.0486 to 0.0513), the same as for the procedure given the true $m_0$ (0.0502). The adaptive procedure found 62.3% of the alternatives against 60.5%. The mean of $\hat\pi_0(0.5)$ was 0.8990 (0.8978 to 0.9009), against the exact expectation 0.90027 of Theorem 4.

Example (the adaptive procedure under dependence). It is tempting to conclude that the adaptive procedure should always replace the plain one, since it never does worse with independent tests. Dependence changes that. The script repeated the simulation with every pair of z-values correlated 0.5, through a shared normal term, so that each null p-value is still uniform. The expectation of $\hat\pi_0$ was still close to 0.9 (median of the set means 0.906), as Theorem 4 promises, but its standard deviation within a seed rose from 0.032 to 0.519. When the shared term is positive, every null p-value moves toward 0 at once: $\hat\pi_0$ comes out small exactly when many nulls are below the threshold, and the adaptive procedure rejects them. Its false discovery rate was 0.127 (interquartile range 0.114 to 0.145), two and a half times the target. The Benjamini–Hochberg procedure stayed below the target in this simulation, at 0.036; The False Discovery Rate and the Benjamini–Hochberg Procedure sets out the forms of dependence under which its guarantee is known to hold. The comparison is an observation of this simulation, but it shows that the adaptive guarantee leans on independence in a way the plain procedure's does not.

The grain terms. With $\hat\pi_0 = 0.346$, $\hat\pi_0 m = 304$, so the estimated false discovery rate of the threshold $t = 0.05$ is

$$\widehat{\mathrm{FDR}}_{0.5}(0.05) = \frac{304 \times 0.05}{466} = 0.0326,$$

against 0.0942 with $\hat\pi_0 = 1$. At $t = 0.01$ there are 364 discoveries and an estimated rate of 0.0084. The procedures compare as follows at two levels:

Level Benjamini–Hochberg ($\hat q$ with $\hat\pi_0 = 1$) Storey's q-values ($\hat\pi_0 = 0.346$) Adaptive procedure
0.05 412 515 514
0.01 317 373

Accepting a 5% false discovery rate, Storey's q-values declare 103 more terms than the Benjamini–Hochberg procedure. The 515th term in the order of the p-values, the last declared, is japanese (stemmed japanes): it appears in 279 stories, only 9 of them about grain, fewer than independence predicts, with $p = 0.0842$ and $\hat q = 0.0497$. Its Benjamini–Hochberg adjusted p-value is 0.143. The next term, just, has $p = 0.0853$ and $\hat q = 0.0502$, and is not declared. For the plain procedure the boundary falls between told ($p = 0.0229$, $\tilde p = 0.0489$) and unit ($p = 0.0237$, $\tilde p = 0.0503$).

Example (a q-value smaller than its p-value). The q-value of japanese, 0.0497, is smaller than its p-value, 0.0842. That can surprise a reader who thinks of the q-value as a p-value made stricter. The estimated rate at rank $k$ is $p_{(k)}$ times $\hat\pi_0 m/k$, and here $\hat\pi_0 m/k = 304/515 < 1$: there are more discoveries below $t = 0.0842$ than the nulls could supply, so most of them are real and the error rate is lower than the level of the single test. A q-value exceeds its p-value only where the discoveries are few relative to $\hat\pi_0 m$.

Every null true: the permuted labels

What does the estimate do when every null hypothesis is true? The 30 label permutations of the first section answer for the grain terms. A permutation keeps each term's frequency and the number of grain stories, so the same 878 terms qualify, and each Fisher p-value is exactly valid.

  • The estimate. $\hat\pi_0(0.5)$ had median 1.093 (interquartile range 1.067 to 1.129), and exceeded 1 in 25 of the 30 permutations. The true value is 1. The excess is the discreteness bias of Theorem 4: the share of p-values at most 0.05 had median 0.0399, below 0.05, and in the permutation drawn in the figure 113 of the 878 p-values fell in the last bin, most of them exactly 1. An estimate above 1 is replaced by 1 in practice.
  • Discoveries. Storey's q-values, with $\hat\pi_0$ capped at 1 (where it is capped they are the Benjamini–Hochberg adjusted p-values), declared some term at 0.05 in 1 of the 30 permutations (3 terms). The False Discovery Rate and the Benjamini–Hochberg Procedure measures the procedure's error rate in a world of permuted labels for all terms.
  • Spread. The interquartile range of $\hat\pi_0(0.5)$ over the permutations was 0.062. For 878 independent, continuous, uniform p-values, Theorem 4 gives a standard deviation of $1/\sqrt{878} = 0.0337$ and, with a normal approximation, an interquartile range of 0.046. The observed spread is wider by about a third. Terms co-occur in stories, so their tests are dependent, and the discreteness also changes the variance; the experiment does not separate the two.
  • The center of the z-values. Writing each table's signed $\chi^2$ root as a z-value, the interquartile range of the 878 z-values had median 1.311 over the permutations, close to the 1.349 of a standard normal. For the real labels it is 4.35. The center of the real distribution is three times as wide as a null distribution, the visible form of the low $\hat\pi_0$.

The empirical Bayes reading

The q-value was defined through a frequentist error rate and turned out to be a posterior probability. Efron and Hastie (2016, Section 15.3) give the same construction a Bayesian start. In the two-groups model for z-values, the posterior probability that a case with $z \ge z_0$ is null, their "Bayes false-discovery rate", is $\mathrm{Fdr}(z_0) = \pi_0 S_0(z_0)/S(z_0)$ (eq. 15.24). The null survival function $S_0$ is known; the mixture's $S(z_0)$ is not, but with thousands of cases its empirical estimate, the share of z-values at least $z_0$, is close to it (eq. 15.25). Substituting gives an empirical Bayes estimate, and they show (eqs. 15.27 and 15.28) that the Benjamini–Hochberg rule at level $\alpha$ is exactly the rule "reject when the estimated $\mathrm{Fdr}$ is at most $\pi_0\alpha$". Storey's $\hat q$ estimates the same posterior probability with $\pi_0$ estimated as well. The information that makes this possible comes from the other cases: what one term's p-value means depends on how the other 877 are distributed. Efron and Hastie compare this "learning from the experience of others" with the James–Stein estimator, which Hierarchical Models and Shrinkage derives as an empirical Bayes rule.

The local version estimates $\mathrm{fdr}(z) = \pi_0 f_0(z)/\hat f(z)$ with a smooth density estimate $\hat f$ fitted to the histogram of the z-values (Efron and Hastie, 2016, eq. 15.39; they fit a fourth-degree polynomial to the log counts by Poisson regression). They describe a cutoff of $\mathrm{fdr} \le 0.2$ for declaring a case interesting, and show (eqs. 15.40 to 15.43) that it amounts to a Bayes factor $f_1(z)/f_0(z)$ of at least $4\pi_0/(1 - \pi_0)$, which is at least 36 when $\pi_0 \ge 0.9$.

Which null? Everything so far assumes the theoretical null: uniform p-values, standard normal z-values. Efron and Hastie (2016, Section 15.5) show a case where the data contradict it. For 2,749 New York City police officers scored for possible racial bias in pedestrian stops, the center of the z-value histogram was much wider than $N(0, 1)$, and a fit to the central data gave an empirical null of $N(0.10, 1.40^2)$ (their eq. 15.47). Under it only four officers reached $\mathrm{fdr} \le 0.2$; under the theoretical null, 125 officers with $z \ge 2.50$ did on the right side alone. Their method assumes that $\pi_0$ is large, at least about 0.9, and that most cases near the center are null.

The grain terms have the same symptom, a center three times too wide, but not the assumption: with $\hat\pi_0 = 0.346$, most of the center is not null. The permutations show that the theoretical null is correct for the hypothesis of independence. An empirical null would answer a different question, which terms stand out from the typical degree of association, and its fitting method is not built for a share of nulls this small. It is not fitted here.

What is proved, cited and observed

Proved here: Lemma 1 ($\mathrm{FDR} = \mathrm{pFDR}\,P(R > 0)$); Theorem 1 (pFDR as a posterior probability, with Storey's argument); Theorem 2 (when the q-value is the pFDR of its own p-value, with concavity for the one-sided $z$ test); Theorem 3 (the tail rate as an average of the local rate); Theorem 4 (the expectation and variance of $\hat\pi_0$); Theorem 5 (q-values and the Benjamini–Hochberg procedure); the almost-sure limit of $\widehat{\mathrm{FDR}}_\lambda(t)$.

Taken from other pages: the Benjamini–Hochberg procedure, its adjusted p-values and its false discovery rate under independence and positive dependence, from The False Discovery Rate and the Benjamini–Hochberg Procedure; the strong law of large numbers; the Mantel–Haenszel test.

Cited: the finite-sample conservativeness of $\widehat{\mathrm{FDR}}_\lambda$ and the control of the adaptive procedure (Storey, Taylor and Siegmund, 2004); the asymptotic results of Storey (2003, Section 5); the two-stage procedure (Benjamini, Krieger and Yekutieli, 2006); the empirical Bayes reading, the local fdr cutoff and the police data (Efron and Hastie, 2016).

Observed in this article's experiments: everything about the grain terms, the permutations and the simulations. They are observations about these data and these designs.

Worked problems

The problems below were posed for this article: one on ten p-values small enough to work by hand, two on the two-groups example, and one on the boundary of the grain example. Every number is recomputed by tools/experiments/statistics/q-values.py, the first problem in exact arithmetic.

Problem 1 (q-values by hand). Ten tests give the p-values 0.001, 0.008, 0.009, 0.03, 0.035, 0.04, 0.27, 0.62, 0.74 and 0.93. Estimate $\pi_0$ with $\lambda = 0.5$, compute the estimated q-values, and compare the discoveries at level 0.05 with those of the Benjamini–Hochberg procedure.

Solution. $\hat\pi_0 = 0.6$; six hypotheses have $\hat q \le 0.05$, against three for the Benjamini–Hochberg procedure. Three p-values exceed 0.5, so $\hat\pi_0 = 3/(10 \times 0.5) = 0.6$ and $\hat\pi_0 m = 6$. The ratios $6p_{(k)}/k$ and $10p_{(k)}/k$, then the minimum over $k \ge i$:

Rank $p$ $6p/k$ $\hat q$ $10p/k$ $\tilde p$
1 0.001 0.006 0.006 0.010 0.010
2 0.008 0.024 0.018 0.040 0.030
3 0.009 0.018 0.018 0.030 0.030
4 0.030 0.045 0.040 0.075 0.0667
5 0.035 0.042 0.040 0.070 0.0667
6 0.040 0.040 0.040 0.0667 0.0667
7 0.27 0.2314 0.2314 0.3857 0.3857
8 0.62 0.465 0.465 0.775 0.775
9 0.74 0.4933 0.4933 0.8222 0.8222
10 0.93 0.558 0.558 0.930 0.930

The minimum over later ranks matters at ranks 2, 4 and 5, where a later ratio is smaller. The first six q-values are at most 0.05 and the seventh is 0.2314, so six hypotheses are declared. The adjusted p-values reach 0.0667 at rank 4, so the Benjamini–Hochberg procedure declares three. By Theorem 5(b), Storey's six are what the procedure declares with $m = 10$ replaced by 6: the largest $k$ with $p_{(k)} \le 0.05k/6$ is $k = 6$, since $0.04 \le 0.05$.

Problem 2 (the two-groups example). In the model with $\pi_0 = 0.9$, one-sided $z$ tests and alternative $N(3, 1)$, verify $\mathrm{pFDR}(0.05) = 0.330$ as a ratio of expected counts for $m = 1{,}000$ tests, and find the q-value of $p = 0.001$.

Solution. The expected number of discoveries is $mF(0.05) = 1{,}000 \times 0.13623 = 136.2$ and the expected number of false ones is $m\pi_0 \times 0.05 = 45$; their ratio is $45/136.2 = 0.330$, the value of Theorem 1, as the remark after it says. For $p = 0.001$, the critical value is $z = 3.090$, the power is $F_1(0.001) = \Phi(3 - 3.090) = 0.4641$, and $F(0.001) = 0.9(0.001) + 0.1(0.4641) = 0.0473$. Since $F_1$ is concave (Theorem 2), the q-value is $\mathrm{pFDR}(0.001) = 0.0009/0.0473 = 0.0190$. The local rate at $z = 3.090$ is 0.071, nearly four times as large.

Problem 3 (a weak alternative). Keep $\pi_0 = 0.9$ but let the alternative be $N(1, 1)$. Find $E[\hat\pi_0(0.5)]$ and its standard deviation for $m = 1{,}000$ independent tests.

Solution. The expectation is 0.9317 and the standard deviation 0.0315. The threshold $p = 0.5$ corresponds to $z = 0$, so $F_1(0.5) = \Phi(1 - 0) = 0.8413$. By Theorem 4,

$$E[\hat\pi_0(0.5)] = 0.9 + 0.1 \times \frac{1 - 0.8413}{0.5} = 0.9 + 0.0317 = 0.9317.$$

A sixth of the alternatives have p-values above one half and are counted, with weight 2, as nulls. For the variance, $F(0.5) = 0.9(0.5) + 0.1(0.8413) = 0.5341$, and

$$\operatorname{sd}[\hat\pi_0(0.5)] = \frac{\sqrt{0.5341 \times 0.4659/1{,}000}}{0.5} = 0.0315.$$

The bias, 0.0317, is as large as the standard deviation, so with weak alternatives a larger $m$ does not make the estimate accurate, only precise.

Problem 4 (the boundary term). Recompute the q-value of japanese in the grain example from its p-value 0.08416 and its rank 515, and say why the next term is not declared at 0.05.

Solution. Its estimated rate is $\hat\pi_0 m\,p_{(515)}/515 = 304 \times 0.08416/515 = 0.0497$. No later rank has a smaller ratio, so this is its q-value (the script checks it). The next term, just, has $p_{(516)} = 0.08526$, and $304 \times 0.08526/516 = 0.0502$, which exceeds 0.05; all later ratios are larger still, so its q-value is 0.0502 and it is not declared. With $\hat\pi_0 = 1$, japanese would have $878 \times 0.08416/515 = 0.143$ at its own rank, which is its Benjamini–Hochberg adjusted p-value.

What we have learned

With many tests, the p-values themselves carry information about how many null hypotheses are true. Above a point such as one half, null p-values are spread evenly and alternatives are scarce, so their count estimates $\pi_0$ conservatively, with a bias that can be written down and a variance that dependence can change, and that positive dependence inflated greatly in the simulation. In the two-groups model the positive false discovery rate of a threshold is the posterior probability that a discovery is null, and the q-value of a test is that probability for the smallest region containing it. Estimated q-values with $\hat\pi_0 = 1$ are the Benjamini–Hochberg adjusted p-values; with Storey's estimate they declare more. On the grain terms the estimate, which is conservative on average, puts the share of terms independent of the category at about a third, and Storey's q-values declare 515 terms where the Benjamini–Hochberg procedure declares 412. A q-value is not the probability that its own hypothesis is null; the local false discovery rate is.

All of this assumes that the hypotheses were fixed before the data were seen and that every test's result is reported. When the data choose which estimate is reported, as when the best of several models is announced, the reported number is biased upward and its interval too short. Selective Inference and the Garden of Forking Paths measures that effect and shows how to correct for it.

References