Why BH Controls FDR Under Independence

Why an Independence Assumption Gives a Useful Guarantee

Genomic analyses may test thousands of hypotheses at once. The Benjamini–Hochberg (BH) procedure is useful in this setting because it controls the expected false discovery proportion without requiring the probability of even one false rejection to be small. The key result here is specific: when the p-values are independent and every true-null p-value is super-uniform, BH’s false discovery rate is at most its target level $q$.

The proof is not obtained by treating each BH rejection threshold as fixed: the threshold depends on the observed p-values, including the p-value being assessed. Instead, a leave-one-out argument fixes all the other p-values and asks what happens when one true-null p-value varies. That argument also makes clear exactly where independence and super-uniformity are used.

Setup and Assumptions

Definition: Consider a fixed family of $m$ hypotheses and p-values $p_1,\ldots,p_m$. Let $m_0$ be the number of true null hypotheses. A true-null p-value $p_i$ is super-uniform if $P(p_i\le t)\le t$ for every $t\in[0,1]$. For this result, assume the p-values are mutually independent, each true-null p-value is super-uniform, and the target level satisfies $0<q<1$. No super-uniformity condition is required for p-values from false null hypotheses.

Order the observed p-values as $p_{(1)}\le\cdots\le p_{(m)}$. BH finds the largest $k$ for which $p_{(k)}\le kq/m$, and rejects the hypotheses corresponding to the first $k$ ordered p-values. If no such $k$ exists, it rejects none. Write $R$ for the number rejected and $V$ for the number of rejected true nulls.

As in the definition of false discovery rate, use the false discovery proportion $V/R$ when $R>0$, and define it to be zero when $R=0$. Thus, in a single expression, it is $V/(R\vee1)$, where $R\vee1=\max(R,1)$. The false discovery rate is the expectation of this proportion over repeated realizations of the p-values.

Theorem: Under the assumptions above, the BH procedure satisfies $$ \operatorname{FDR}=E\left[\frac{V}{R\vee1}\right]\le \frac{m_0}{m}q\le q. $$ The first bound can be more informative when fewer than $m$ hypotheses are true nulls. When all hypotheses are true nulls, it gives the stated level $q$.

The Leave-One-Out Argument

For each true-null hypothesis $i$, hold the other $m-1$ p-values fixed. Let $R_i$ be the number of BH rejections that would occur if $p_i$ were replaced by zero. Since the other p-values are held fixed, $R_i$ does not depend on the actual value of $p_i$. Replacing a p-value by zero can only make the ordered p-values smaller, so $R_i$ is at least as large as the rejection count obtained from any value of $p_i$ in $[0,1]$.

The essential leave-one-out fact is that, if $R_i>0$, hypothesis $i$ is rejected exactly when $p_i\le qR_i/m$; in that event the actual rejection count is $R_i$. To see this, first suppose $p_i\le qR_i/m$. In the zero-replacement calculation, at least $R_i$ p-values are at most $qR_i/m$. Replacing zero by $p_i$ preserves at least $R_i$ such p-values, so the actual count is at least $R_i$. It cannot exceed $R_i$, because replacing zero by a value at least zero cannot increase the BH rejection count. Therefore the count remains $R_i$, and $i$ is among the rejected hypotheses.

Conversely, suppose $i$ is rejected in the actual calculation, which has $R$ rejections. Then $p_i\le qR/m$. Replacing $p_i$ by zero preserves at least $R$ p-values at or below the $R$th threshold. It cannot create a rejection beyond $R$: because $i$ was among the first $R$, changing its value to zero leaves the order statistics beyond rank $R$ unchanged. Hence $R_i=R$, and $p_i\le qR_i/m$, as claimed. If $R_i=0$, no value of $p_i$ can produce a rejection, because zero is already the smallest possible replacement.

Bounding Each True-Null Contribution

To handle the case of no rejections without using an undefined ratio, define the contribution of hypothesis $i$ by $$ W_i= \begin{cases} \mathbf{1}\{i\text{ is rejected}\}/R,&R>0,\\ 0,&R=0. \end{cases} $$ Then, for every outcome, the false discovery proportion is the sum of these contributions over true nulls. If $R>0$, each rejected true null contributes $1/R$, so the sum is $V/R$. If $R=0$, there are no rejected true nulls and both sides are zero.

The leave-one-out fact gives, when $R_i>0$, $$ W_i=\frac{\mathbf{1}\{p_i\le qR_i/m\}}{R_i}. $$ When $R_i=0$, $W_i=0$. Now condition on all the other p-values. Mutual independence means the conditional distribution of the true-null $p_i$ is still its marginal distribution. Super-uniformity therefore bounds the conditional probability of crossing the cutoff by that cutoff itself: $$ E[W_i\mid p_j,\ j\ne i] =\frac{P(p_i\le qR_i/m\mid p_j,\ j\ne i)}{R_i} \le \frac{qR_i/m}{R_i} =\frac{q}{m},\qquad R_i>0. $$ If $R_i=0$, the conditional expectation is zero, which is also at most $q/m$. Taking expectations preserves the bound, so $E[W_i]\le q/m$ for every true null.

Summing over the $m_0$ true nulls completes the justification:

\operatorname{FDR} =E\left[\frac{V}{R\vee1}\right] =\sum_{i\text{ true null}}E[W_i] \le \sum_{i\text{ true null}}\frac{q}{m} =\frac{m_0}{m}q \le q.

This proof uses the adaptive BH cutoff rather than pretending it is fixed. The leave-one-out count $R_i$ is determined by the other tests, which is why conditioning makes the threshold suitable for applying the true-null p-value bound.

Worked Example: Checking the BH Rejections

Consider a hypothetical family of five tests at $q=0.10$, with ordered p-values $0.004,\ 0.018,\ 0.041,\ 0.22,\ 0.70$. Suppose the first is from a false null and the next two are from true nulls; the last two are also from false nulls.

The BH thresholds for ranks one through five are $0.10/5=0.0200$, $2(0.10)/5=0.0400$, $3(0.10)/5=0.0600$, $4(0.10)/5=0.0800$, and $5(0.10)/5=0.100$. The first three comparisons are $0.004\le0.0200$, $0.018\le0.0400$, and $0.041\le0.0600$. The fourth and fifth fail: $0.22>0.0800$ and $0.70>0.100$. Thus the largest passing rank is three, and BH rejects the first three hypotheses.

Here $R=3$, $V=2$, and the realized false discovery proportion is $2/3=0.667$. This single realization does not contradict the FDR guarantee: FDR is an expectation over repeated realizations, not a bound on the false discovery proportion in every particular data set.

Worked Example: A Conditional Leave-One-Out Bound

Suppose $m=4$, $q=0.20$, and the three p-values other than a particular true-null $p_i$ are $0.01,\ 0.07,\ 0.80$. To find $R_i$, insert zero and apply BH. The ordered values are $0,\ 0.01,\ 0.07,\ 0.80$, and the thresholds are $0.05,\ 0.10,\ 0.15,\ 0.20$. The first three pass and the fourth fails, so $R_i=3$.

With the other p-values fixed, $i$ is rejected exactly if $p_i\le qR_i/m=(0.20)(3)/4=0.15$, and then its contribution is $1/3$. Independence and super-uniformity imply $$ E[W_i\mid p_j,\ j\ne i] =\frac{P(p_i\le0.15\mid p_j,\ j\ne i)}{3} \le\frac{0.15}{3}=0.0500=\frac{q}{m}. $$ For example, if the observed $p_i$ were $0.12$, it would be rejected and contribute $1/3$. If it were $0.30$, it would not be rejected and would contribute zero. The bound concerns the conditional expectation across possible values of $p_i$, not either individual contribution.

Worked Example: Using the Family-Level Bound

Consider a hypothetical analysis with $m=8$ tests, of which $m_0=5$ null hypotheses are true, and use $q=0.10$. If the p-values meet the independence and super-uniformity assumptions, the theorem gives $$ \operatorname{FDR}\le\frac{5}{8}(0.10)=0.0625. $$ Thus the expected false discovery proportion is no greater than $0.0625$, or $6.25\%$, under repeated realizations satisfying the stated model. The result does not say that every selected list has at most a $6.25\%$ false proportion. If the number of true nulls were unknown, the general guarantee $\operatorname{FDR}\le q=0.10$ would still follow from $m_0\le m$.

Assumption Checks, Alternatives, and Limitations

The assumptions refer to the p-values under the testing model, not merely to the appearance of the observed p-value list. A true-null test must have $P(p_i\le t)\le t$ across repeated samples for every $t$ in the unit interval. The p-values must also be mutually independent for the conditioning step used here. In practice, independence is a substantive feature of the joint data-generating process; it cannot be confirmed just because the p-values have been sorted or because a dataset contains many tests.

If a true-null p-value is not super-uniform, the probability bound at the BH cutoff need not hold. If a true-null p-value depends on the others, conditioning on them can change its distribution, so the conditional inequality in the proof is no longer justified. In either case, this independence proof does not establish FDR control. Dependence among genomic tests therefore requires a separate justification for the chosen procedure and dependence conditions; it is not resolved by applying the independent-case result unchanged.

The guarantee is also specific to the fixed family of $m$ hypotheses being tested. Changing the family changes the ranks and thresholds in BH, and thus changes the procedure to which the theorem applies. Finally, the bound is about an expectation: a realized false discovery proportion can be above $q$, sometimes substantially so, without violating the theorem.

BH is a step-up multiple-testing procedure, whereas methods such as Holm’s procedure target familywise error, the probability of at least one false rejection. These criteria answer different questions, so a stronger familywise guarantee should not be inferred from this FDR result. The independence proof is particularly useful because it gives a transparent bound, $(m_0/m)q$, but its assumptions must be appropriate before that bound is used.

Common Pitfall

Common mistake: Write the contribution of every test as $\mathbf{1}\{i\text{ is rejected}\}/R$, then proceed as though it is defined even when $R=0$. When there are no rejections, this becomes $0/0$, which is undefined. Correction: Define the contribution as zero when $R=0$, and use the ratio only when $R>0$. Then the decomposition of the false discovery proportion and the leave-one-out argument are valid in both cases.

A second, related mistake is to say the theorem guarantees that at most a fraction $q$ of the rejections in each analysis are false. It guarantees an upper bound on the expected false discovery proportion under its assumptions; an individual realization can have a larger fraction.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

State the assumptions needed for the independence-based BH bound. Is super-uniformity required for false-null p-values?
For $m=6$, $q=0.12$, and $R_i=2$, calculate the leave-one-out cutoff and the upper bound on the conditional expected contribution of true-null test $i$.
If $R=0$, what is the false discovery proportion, and why is it not appropriate to leave the expression as $V/R$?
Suppose $m=10$, $m_0=4$, and $q=0.05$. What family-level FDR bound follows under the theorem?

Solutions. (1) The p-values are mutually independent, each true-null p-value is super-uniform, and $0<q<1$. No super-uniformity assumption is needed for false-null p-values. (2) The cutoff is $qR_i/m=(0.12)(2)/6=0.0400$. The conditional expected contribution is at most $0.0400/2=0.0200=q/m$. (3) It is defined to be zero. Since $V=0$ when $R=0$, writing $V/R$ would give the undefined expression $0/0$, not a valid value. (4) The bound is $(m_0/m)q=(4/10)(0.05)=0.0200$, or $2.00\%$.