BH Control Under PRDS Dependence

Why the Dependence Assumption Matters

Genomic analyses often test many hypotheses whose test statistics are dependent. The Benjamini–Hochberg (BH) procedure can still control the false discovery rate under a particular positive-dependence condition, but valid p-values by themselves do not imply that guarantee. The condition is PRDS on the subset of true null hypotheses: informally, as a true-null p-value increases, the conditional probability of an increasing event in the full p-value vector does not decrease.

The result concerns the expected proportion of rejections that are false, not a promise that every realized discovery list has a small false-discovery proportion. The proof also uses the shape of the BH step-up thresholds. We will isolate the contribution from one true null, bound it using PRDS, and then sum those bounds across true nulls.

Definition: Consider a fixed family of $m$ hypotheses with p-values $P_1,\ldots,P_m$. Let $I_0$ be the set of true null indices and $m_0=|I_0|$. A true-null p-value is marginally valid if $P(P_i\le u)\le u$ for every $u\in[0,1]$ and every $i\in I_0$. A set $D\subseteq[0,1]^m$ is increasing if $x\in D$ and $y_j\ge x_j$ for every coordinate $j$ imply $y\in D$. The p-value vector is PRDS on $I_0$ if, for every $i\in I_0$ and every increasing measurable set $D$, $P((P_1,\ldots,P_m)\in D\mid P_i=x)$ is nondecreasing in $x$, wherever the conditional probabilities are defined.

The definition uses the usual coordinatewise order on p-values: increasing a p-value means moving toward less evidence against its null. One useful consequence is that, for any decreasing set $A$, $P((P_1,\ldots,P_m)\in A\mid P_i\le t)$ is nonincreasing in $t$. Indeed, the complement of $A$ is increasing; its conditional probability given $P_i=x$ is nondecreasing in $x$, and averaging over $P_i\le t$ preserves that ordering as $t$ grows. This consequence will be applied to the number of rejections when one p-value is fixed at zero.

The BH Rule and Its Guarantee

Write the ordered p-values as $P_{(1)}\le\cdots\le P_{(m)}$. For a chosen level $q\in(0,1)$, the BH thresholds are $t_r=qr/m$, for $r=1,\ldots,m$. The procedure sets $R$ to the largest $r$ for which $P_{(r)}\le t_r$, with $R=0$ if no such $r$ exists, and rejects the hypotheses with p-values at most $t_R$. Ties at the rejection boundary are included.

Let $V$ be the number of rejected true nulls. The false discovery proportion is $V/(R\vee1)$, where $R\vee1$ is the larger of $R$ and 1. Its expectation, the false discovery rate, is $\mathrm{FDR}=E[V/(R\vee1)]$.

Theorem: If all true-null p-values are marginally valid and the full p-value vector is PRDS on $I_0$, then the BH procedure at level $q$ satisfies $$ \mathrm{FDR}\le \frac{m_0}{m}q\le q. $$ The dependence condition is on the full vector in the PRDS definition, with monotonicity required for each true-null coordinate. No particular dependence condition is required among the nonnull p-values beyond what is implied by this PRDS assumption.

The key step is an individual-null bound. For each $i\in I_0$, the expected contribution of that hypothesis to the FDR is at most $q/m$. The proof below makes explicit how PRDS controls the relevant joint events; marginal validity alone cannot provide that control.

Justifying the Step-Up Bound

Fix a true-null index $i$. Let $R_i$ be the number of BH rejections after replacing $P_i$ by zero and leaving all other p-values unchanged. For fixed values of the other p-values, lowering $P_i$ to zero cannot reduce the BH rejection count. Moreover, if $P_i$ is rejected in the original procedure, then replacing it by zero does not change the rejection count: it was already among the p-values below the rejection threshold. Conversely, if $P_i\le qR_i/m$, restoring $P_i$ still leaves at least $R_i$ p-values below the $R_i$-th threshold, and cannot create a count greater than $R_i$. Thus $P_i$ is rejected exactly when $P_i\le qR_i/m$, and on that event $R=R_i$.

For $r=1,\ldots,m$, define $A_r=\{R_i\ge r\}$, and let $A_{m+1}$ be empty. With $P_i$ replaced by zero, the BH rejection count is nonincreasing in every other p-value. Therefore $A_r$ is a decreasing event in the full vector. Define $G_r(t)=P(A_r\mid P_i\le t)$, with $G_{m+1}(t)=0$. The PRDS consequence above shows that each $G_r(t)$ is nonincreasing in $t$. Also $0\le G_1(t)\le1$.

Partition the contribution from $i$ according to the possible values of $R_i$. Since $A_r\setminus A_{r+1}=\{R_i=r\}$, marginal validity gives

\begin{aligned} E\left[\frac{\mathbf{1}\{i\text{ is rejected}\}}{R\vee1}\right] &=\sum_{r=1}^{m}\frac{1}{r}P(P_i\le t_r,\ R_i=r)\\ &\le \frac{q}{m}\sum_{r=1}^{m}\bigl[G_r(t_r)-G_{r+1}(t_r)\bigr]. \end{aligned}

For the inequality, the probability in each summand is exactly $P(P_i\le t_r)\{G_r(t_r)-G_{r+1}(t_r)\}$. The bracket is nonnegative, and $P(P_i\le t_r)\le t_r=qr/m$; dividing by $r$ gives the stated bound. To see why the PRDS monotonicity makes the sum no greater than one, re-index its second part:

\begin{aligned} \sum_{r=1}^{m}\bigl[G_r(t_r)-G_{r+1}(t_r)\bigr] &=G_1(t_1)+\sum_{r=2}^{m}\bigl[G_r(t_r)-G_r(t_{r-1})\bigr]-G_{m+1}(t_m)\\ &\le G_1(t_1)\le 1. \end{aligned}

Here $t_r\ge t_{r-1}$, so each difference in the middle sum is nonpositive; the last term is zero by definition. This proves the individual-null bound $q/m$. Summing it over the $m_0$ true nulls proves the theorem.

Worked Applications

Worked Example: Applying BH to a Hypothetical Genomic Screen

Suppose a hypothetical screen tests $m=6$ features at $q=0.10$, with ordered p-values $0.001, 0.012, 0.028, 0.070, 0.310, 0.800$. The BH thresholds are $0.10r/6$, or approximately $0.01667, 0.03333, 0.05000, 0.06667, 0.08333, 0.1000$.

At rank 3, $0.028\le0.05000$, so rank 3 meets its threshold. At rank 4, $0.070>0.06667$, and ranks 5 and 6 also fail their thresholds. Thus $R=3$, and the first three hypotheses are rejected.

For illustration, suppose the first and third hypotheses are true nulls and the others are nonnull. Then this realized list has $V=2$, $R=3$, and false discovery proportion $2/3$. This does not contradict the theorem: the theorem bounds the expectation over repeated realizations under its assumptions, not the false discovery proportion in every single list. If $m_0=2$, the bound is $(2/6)(0.10)=0.03333$.

Worked Example: How the PRDS Summation Bounds One Null

Consider a hypothetical illustration of the summation in the proof with $m=3$ and $q=0.12$, so $t_1=0.04$, $t_2=0.08$, and $t_3=0.12$. Suppose the conditional probabilities $G_r(t)$ take the following values at the needed thresholds: $G_1(t_1)=0.90$; $G_2(t_1)=0.55$, $G_2(t_2)=0.45$; and $G_3(t_1)=0.25$, $G_3(t_2)=0.20$, $G_3(t_3)=0.15$. These values obey the required nonincreasing behavior as $t$ grows, and $G_4(t)=0$.

The three terms in the sum are $G_1(t_1)-G_2(t_1)=0.90-0.55=0.35$, $G_2(t_2)-G_3(t_2)=0.45-0.20=0.25$, and $G_3(t_3)-G_4(t_3)=0.15-0=0.15$. Their total is $0.75$, which is at most 1. The individual-null contribution is therefore at most $(q/m)(0.75)=(0.12/3)(0.75)=0.0300$, below the general bound $q/m=0.0400$. This is an illustration of the proof’s conditional-probability bookkeeping, not a claim that these values describe a particular genomic data set.

Worked Example: Why True-Null Independence Alone Is Not Enough

Let $m=2$, $m_0=1$, and let the true-null p-value $P_1$ be uniform on $[0,1]$. Define the nonnull p-value $P_2$ to equal 1 when $P_1\le q/2$, to equal 0 when $q/2<P_1\le q$, and to equal 1 otherwise. The lone true-null p-value is valid, and independence among true-null p-values is vacuous in this example.

When $P_1\le q/2$, BH rejects $P_1$ alone: $P_1$ meets the first threshold $q/2$, while the second ordered p-value is 1 and exceeds $q$. This event has probability $q/2$ and FDP 1. When $q/2<P_1\le q$, the ordered p-values are 0 and $P_1$; both meet the rank-2 threshold $q$. This event also has probability $q/2$, and its FDP is $1/2$. Outside these events there are no rejections. Therefore

\mathrm{FDR}=\frac{q}{2}(1)+\frac{q}{2}\left(\frac{1}{2}\right)=\frac{3q}{4}, \qquad \frac{m_0}{m}q=\frac{q}{2}.

Since $3q/4>q/2$ for $q>0$, independence among true-null p-values alone does not establish the usual BH bound. Here the nonnull p-value depends on the true-null p-value in a way not covered by the required PRDS condition.

Assumptions, Diagnostics, and Alternatives

The theorem requires a fixed testing family, marginal validity for each true null, and PRDS on the subset of true nulls. Marginal validity means that each true-null p-value is superuniform; it does not mean that the p-values are mutually independent. PRDS is a condition on the joint distribution and is stronger than observing positive pairwise correlations among test statistics or p-values. Pairwise correlations alone do not establish the conditional monotonicity for every increasing set.

In practice, the true-null subset is usually unknown, and PRDS is a modeling assumption rather than something confirmed by a single diagnostic plot. Researchers can inspect dependence patterns, study the construction of the test statistics, and use simulations under plausible null-generating models to assess whether the assumption is credible. Such checks can reveal concerning patterns, but cannot prove PRDS for all relevant events. When the assumed dependence structure is doubtful, the stated theorem does not certify the BH bound; a procedure with a guarantee under more general dependence is an alternative, though it can be more conservative.

Under independence of all p-values, with valid true-null p-values, the BH guarantee also holds; this is a sufficient special case, not the same as independence among true-null p-values alone. Under PRDS, dependence is allowed, but its direction and conditional structure matter. The result is useful in genomic settings because it explains when BH can retain its FDR guarantee without requiring full independence.

Common Mistakes

Using marginal validity to bound a joint event. $P(P_i\le t)\le t$ does not by itself bound $P(P_i\le t,\ R=r)$. The proof needs PRDS to control how the rejection-count events behave conditionally as the cutoff changes.
Calling the realized FDP the FDR. $V/(R\vee1)$ is the realized proportion; FDR is its expectation across repetitions of the procedure under the model.
Assuming true-null independence is sufficient. Dependence between true-null and nonnull p-values can still affect the BH rejection count. A valid sufficient independence condition is independence of all p-values, alongside true-null validity.
Treating positive correlation as proof of PRDS. Pairwise positive correlations do not verify the required conditional monotonicity over increasing sets.

Key takeaway: BH control under PRDS follows by bounding each true-null contribution by $q/m$. Marginal validity supplies the cutoff probability bound, while PRDS supplies the monotonicity that makes the step-up sum at most one.

Check Your Understanding

Answer each question, then compare with the solutions below.

For $m=8$ and $q=0.05$, what is the BH threshold at rank 4?
If $m=10$, $m_0=3$, and the PRDS assumptions hold at $q=0.10$, what FDR bound does the theorem give?
Why does marginal validity alone not bound $P(P_i\le t_r,\ R_i=r)$ by $t_r$ times a useful rejection-count probability?
What is the difference between the FDP and FDR?
Does independence among true-null p-values alone guarantee the BH bound when nonnull p-values can depend on them?

Solutions. (1) $t_4=0.05(4)/8=0.0250$. (2) The bound is $(3/10)(0.10)=0.0300$. (3) Validity bounds only $P(P_i\le t_r)$; the joint event also involves $R_i$, which can depend on $P_i$. The PRDS monotonicity argument controls the conditional rejection-count probabilities used in the step-up sum. (4) FDP is the realized ratio $V/(R\vee1)$, while FDR is its expectation. (5) No. Dependence between true-null and nonnull p-values can invalidate the guarantee, as the two-test construction above demonstrates.