Benjamini–Hochberg procedure
Section of High-dimensional analysis, part of Statistical learning
Benjamini–Hochberg procedure
| Type | Section |
| Taught in | High-dimensional analysis |
| Part | Statistical learning |
Test m null hypotheses H_1,\ldots,H_m whose p-values are P_1,\ldots,P_m. Before the data are collected these are random variables. Order them P_{(1)}\le P_{(2)}\le\cdots\le P_{(m)} and let H_{(i)} be the hypothesis whose p-value is P_{(i)}.
Definition 1 (Benjamini–Hochberg) Let k be the largest i for which P_{(i)}\le (i/m)\,q^*. Then reject all H_{(i)} for i=1,\ldots,k. Reject none if no such i exists.
Theorem 1 (Benjamini–Hochberg controls the false discovery rate) Suppose the p-values are mutually independent and each true-null p-value is valid: \mathbb{P}(P_i\le t)\le t for 0\le t\le 1. The procedure at q^*\in(0,1) satisfies
\mathrm{FDR}\le\frac{m_0}{m}q^*\le q^*.
Equality holds in the first inequality for exactly uniform null p-values (Benjamini and Hochberg, 1995; Benjamini and Yekutieli, 2001).
Article: Benjamini–Hochberg controls the false discovery rate →
The argument below is for independent p-values with exactly uniform null p-values. The denominator R depends on all the tests, including the one whose false-rejection probability is wanted. Remove that dependence by setting the selected null p-value to zero. This gives a rejection count determined only by the other p-values. The cancellation is then between its appearance in the threshold and in the denominator.
Write q=q^* and let N be the true-null set. For i\in N, let R_i be the rejection count after replacing P_i by zero. Then R_i\ge 1. If H_i is rejected, lowering its already-rejected p-value cannot create a new crossing at an index greater than R, so R_i=R. Conversely, if P_i\le q R_i/m, restoring P_i retains at least R_i values below that threshold. It cannot increase the count above the count obtained with zero, so R=R_i and H_i is rejected. Hence
\frac{V}{R\vee 1}=\sum_{i\in N}\frac{I(P_i\le q R_i/m)}{R_i}.
Condition on all p-values except P_i. Independence and exact null uniformity give \mathbb{P}(P_i\le q R_i/m\mid R_i)=q R_i/m, so each summand has expectation q/m. Summing gives \mathrm{FDR}=m_0 q/m. For super-uniform null p-values, replace equality by an upper bound in the conditional probability.
Independence is sufficient, not necessary. The procedure also controls the false-discovery rate under positive regression dependence on the true nulls. Arbitrary correlation is not that condition. For arbitrary dependence, and for valid marginal p-values, replace q^* by q^*/c(m), where c(m)=\sum_{j=1}^{m} 1/j. Reject through the largest i satisfying P_{(i)}\le i q^*/[m\,c(m)]. The price of the broader guarantee is a smaller threshold.
Example 1 (Benjamini–Hochberg by hand) Question. Ten sorted p-values are 0.0002, 0.0009, 0.0041, 0.0121, 0.0230, 0.0302, 0.0420, 0.2400, 0.5200, 0.8900. Apply the procedure at m=10 and q^*=0.05, and compare with Bonferroni and with the unadjusted rule.
Solution. The thresholds i q^*/m are 0.005, 0.010, 0.015, and so on up to 0.050. Comparing: p_{(5)}=0.0230\le 0.025 holds, p_{(6)}=0.0302\le 0.030 fails by a hair, and p_{(7)}=0.0420>0.035. The largest i meeting the condition is k=5: reject the five smallest. Bonferroni at 0.05/10=0.005 would reject only three (0.0002, 0.0009, 0.0041), and the unadjusted rule at 0.05 would reject seven. The Benjamini–Yekutieli thresholds are those divided by c(10)=2.929 and give k=3. The rule takes the largest i for which p_{(i)} lies on or below the line i q^*/m and rejects everything up to it. In this example every earlier p-value is also below its own threshold. That need not happen.
One simulated family of 1{,}000 tests shows the same comparison as a picture: ordered p-values against the line i q/m, and rejection counts for the unadjusted rule, Bonferroni, and Benjamini–Hochberg. The step-up rule rejects more than Bonferroni and fewer than the unadjusted threshold.
Marginal testing can identify several correlated coordinates because each has an association with the response. A lasso fit instead considers them jointly and may retain only some interchangeable predictors. Neither procedure is guaranteed to select an entire correlated group, or exactly one representative. Their objectives differ before any particular selection occurs.
Used in
See also
Rank bound · Family-wise control implies false-discovery control · Benjamini–Hochberg · Benjamini–Hochberg controls the false discovery rate · Why classical methods fail when p > n · Rank of the sample covariance · Regression when p > n · Where high-dimensional columns come from