Understanding the Benjamini-Hochberg method proof

I'm trying to understand the proof in Benjamini & Hochberg's 1995 paper, specifically the Lemma in the appendix, as the rest of the proof is short and follows it.

I got stuck somewhere after equation (5)—where it says: "Thus all $$m_0+j_0$$ hypotheses are rejected"—why is that? By which procedure? Procedure (1) (=BH)? Or by using the cutoff declared earlier? (largest j satisfying $$p_j \le \frac{m_0+j}{m+1}q^*$$—which I understand is defined only for the False Null) This would only be true if we indeed fix the cutoff value, which is defined only on the False Null (i.e. discoveries) and simply reject any p-value below this. But I don't immediately see how this is true if we use procedure (1)…

Also the first inequality of equation (6) seems to me wrong—it should be equality, as $$p''$$ is defined to be the value it's replaced with...

In any case after that I completely get lost until equation (8). I have no idea how they arrive that there must be a $$k\le m_0+j-1$$ for which $$p_{(k)}\le{k/(m+1)}q^*$$—what is that $$j$$? Why $$-1$$?

From (8) onward it's understood.

Benjamini, Y., & Hochberg, Y. (1995). Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing. Journal of the Royal Statistical Society. Series B (Methodological), 57(1), 289–300.

• I made a tutorial video about another proof, if anyone is interested youtu.be/PGD8XkDQ2Tw Commented Jul 29, 2021 at 11:35
• This answer here is also great in order to understand the BH method. Commented Mar 28, 2023 at 15:26

Let's backup and give more context to the two cases specified by equation (5), and then clarify the reasoning behind some of the details.

In equation (5), we consider the two cases, $$p \leq p''$$ and $$p > p''$$

1. $$P'_{m_0} =p\leq p''$$

This is a difficult (rare) case because all the $$m_0$$ p-values associated with true nulls are small, and they are likely mixed with false nulls that also have small p-values. By definition of $$P'_{m_0} = p \leq p''$$, all the true hypotheses (along with $$j_0$$ false ones) will get rejected by the procedure and we make the maximum error among those $$m_0$$ true hypotheses. The saving grace is that hopefully $$m_0$$ is small, or it's very rare (that many Unif(0,1) variables would be smaller than those p-values associated with truly false variables).

"Thus all $$m_0 + j_0$$ hypotheses are rejected"—why is that? By which procedure? Procedure (1) (=BH)? Or by using the cutoff declared earlier?

Under $$p\leq p''$$, procedure BH(1) and inequality (4) are effectively describing the same procedure when we consider all true and false hypotheses. It might help to think of the RHS of (4) $$:= p''$$ as an upper bound on the cutoff described in procedure BH(1) where we think about the index $$i$$ as $$m_0 + j$$. Note that at $$P'_{m_0}$$, the RHS of (1) and (4) are equal, and the $$k$$ from BH (1) will be $$k = m_0 + j_0$$ because the maximum of all the true hypotheses are also below this threshold $$p''$$. I believe the main reason to introduce the inequality like this is for the proof to go through, with the intuition that controlling FDR is limited by the unknown proportion of our tests that are actually true $$\left(\frac{m_0}{m}\right)$$.

2. $$P'_{m_0} = p > p''$$

This case is more interesting (common) since our true null p-values are not completely mixed with the false null p-values. Since the true null p-values $$P'_{i} \sim Unif(0,1)$$, we expect many to fall well above the threshold of rejection (well, at least one, the maximum $$P'_{m_0}$$), but the goal is to quantify the extent that this happens, which is where we use the induction hypothesis (IH). I think the cleverness here, is that by conditioning out the highest true null p-value $$P'_{m_0}$$, we can create "new" p-values for a sub-problem with $$m$$ p-values to allow use of the IH.

I have no idea how they arrive that there must be a k such that $$i \leq k \leq m_0 + j - 1$$ for which $$p_{(k)} \leq \{k / (m+1)\}q^*$$ —what is that $$j$$? Why $$−1$$?

Under the condition $$P'_{m_0} = p > p''$$, we are certain that at least 1 value will not be rejected, the hypothesis associated with $$P'_{m_0}$$. Again, it's useful to think of $$p''$$ as an upper bound on the cutoff provided by BH (1). Even though these cutoff values for inequality (4) are defined on only the false nulls, no matter how $$P'_{m_0}$$ lands among the false p-values, $$P'_{m_0} > p''$$ exceeds the upper bound of the rejected p-values of the BH condition always since the upper bound of (4) does not change for true null p-values (in the plot, dashed line only inflects upwards on false nulls).

The $$j$$ here is the same $$j$$ preceding equation (4). The "$$-1$$" is here because we're creating a sub-problem by conditioning on the maximum true null p-value. The maximum value of $$j$$ is $$m_1$$, so the largest our sub-problem is $$m_0 + m_1 - 1 = m$$.

We create the associated sub-problem by creating new Unif(0,1) random variables dividing by the maximum $$p$$, and it happens that the new selection problem has $$m_0 + j - 1$$ p-values, associated with the constant $$\frac{m_0 + j - 1}{(m+1)p}q^*$$.

From here, the proof is largely algebraic, and it seems you understand the remaining portions.

For completeness and the curious, associated code for the plot is below!

qs <- .05 # FDR control rate
m0 <- 4 # num true H0
m1 <- 6 # num false H0
ix <- 1:10 # Index of all true/false H0
jx <- c(1, 1, 2, 2, 3, 3, 4, 5, 5, 6) # Index increases when H0 false
pval <- c(.001, .0015, .002, .0035, .0075, .02, .037, .06, .075, .1)
plot(ix, pval,
xlim = c(1, 10),
ylim = c(0, .1),
col = c(2, 3, 2, 3, 2, 3, 2, 2, 3, 2),
cex = 1.5,
pch = 19,
xlab = "Ordered Null Index",
ylab = "p-values",
xaxt = "n")
title(main =
'Comparison of inequality (4) and BH Rejection (1) when p > p"')
lines(ix, ix / 10 * qs, col = rgb(0,0,0, alpha = .5), lwd = 4) # BH cutoff
lines(ix, (m0 + jx) / (m0 + m1) * qs, lty=2) # (4) RHS

# Various labels and legends
text(9, .075, expression("P'"[m[0]]), pos = 3, cex = 1.1, col = 3)
text(7.2, .0355, expression("p"[j[0]]), pos = 1, cex = 1.1, col = 2)
text(7, .04, 'p"', pos = 3, cex = 1.1)
axis(1, at = 1:10, labels = c("1", "2", "3", "4", "5", "k = 6",
expression(7 ~ (j[0] ~"="~ 4)), "8", "9", "10"))
legend("topleft", lty = c(1, 3), lwd = c(4, 1),
legend = c("BH cutoff (1)", "Inequality (4)"))
legend(x = .64, y = .0909, col = c(3, 2), pch= c(19, 19),
legend = c("True Null", "False Null"))

• +1 for the graph. The 1st part is essentially that the cut-off is after both lines coincide. The 2nd part is when the cut-off is before they coincide. In that case, as you said, at-least 1 hypothesis will not be rejected. I realize now that the -1 comes from the fact that if it wasn't for it, it would mean we are back again in the 1st part. Note that the sub-problem is on the $m_0 + j - 1:=m'\le m$ hypotheses before the cut off. Commented May 16, 2021 at 11:29