betaFeedback

WorksMathematics

Optimal Certified Multiple Testing with E-values

Abstract

We study randomized multiple testing with e-values under arbitrary dependence and introduce a conditional certification constraint: Given the observed evidence, each coordinate's expected rejection certificate must not exceed its e-value. Existing randomized e-BH improvements satisfy this constraint but have no established optimality guarantee. We prove that the maximum conditional inclusion probability for hypothesis ii, given e-values~xx, is 1∧(α/K)∑jmin⁡(xi,xj)1 \wedge (α/ K) \sum_j \min(x_i, x_j), and construct one rule attaining these bounds simultaneously. The rule uses a single independent uniform variable, rejects a prefix of the ordered e-values, and has a unique conditional rejection-set law among rules attaining all the bounds. It therefore maximizes every nonnegative weighted sum of inclusion probabilities, including expected true discoveries under any truth configuration. Under a shared uniform draw, its rejection set contains those of e-BH and U-eBH. The construction extends to BY-calibrated p-values, and simulations under positive and negative dependence show power gains over existing randomized procedures.

Introduction

Multiple testing problems routinely involve dependence among the hypotheses that is unknown or too complex to model, so a procedure must control the false discovery rate (FDR) without relying on a particular dependence structure. The Benjamini–Hochberg (BH) procedure controls the FDR when the null p-values are independent [1] and remains valid under positive regression dependence on a subset [2]; under arbitrary dependence, control is recovered by a correction that lowers the level at which each hypothesis is tested, at a cost in power that grows with the number of hypotheses [2]. The e-BH procedure of Wang and Ramdas [13] avoids the correction by operating on e-values, nonnegative statistics whose expectations under the null hypotheses are bounded by one [12]. Each e-value is only required to satisfy its own marginal expectation bound, and FDR control follows under arbitrary dependence among the coordinates.

Dependence-robust validity therefore follows from the marginal bounds alone, and the question of how effectively the observed evidence is converted into discoveries is left open by the validity guarantee itself.

Improving the power of e-value-based multiple testing while preserving its dependence-robust guarantees has consequently attracted considerable attention. One established route exploits information beyond the marginal evidence. Weighting assigns hypothesis-specific weights to p-values before applying a multiple testing procedure, and increases discoveries when the weights favor the alternatives, with validity preserved as long as the weights are independent of the p-values [6]; Ignatiadis et al. [7] extend the construction to e-values, using an e-value as an unnormalized weight for a p-value. A second route uses distributional information about the null. Wang and Ramdas [13] show that the power of e-BH can be boosted when the marginal null distribution of each e-value is known, Lee and Ren [8] construct boosted e-values through conditional calibration, and Blier-Wong and Wang [4] derive improved e-value thresholds under additional distributional assumptions. Both routes depend on the accuracy of the auxiliary or distributional information, and their validity is tied to the assumptions under which that information is obtained.

A different route, introduced by Xu and Ramdas (2025), uses external randomization and requires no additional information. The underlying operation is stochastic rounding, which replaces a nonnegative evidence value by one of the two adjacent grid points with probabilities chosen so that its expectation is preserved. The operation predates its application to multiple testing: it is standard in numerical analysis, where it controls accumulated rounding error ([5]), and for a single e-value at a fixed threshold it is the randomized Markov inequality of Ramdas and Manole [9], which rejects with probability equal to the product of the test level and the e-value, truncated at one, and is never less powerful than the deterministic threshold rule. Extending the operation to the data-dependent thresholds of e-BH, and to jointly randomized decisions across coordinates, is due to Xu and Ramdas (2025). Their procedures coordinate the rounding across hypotheses through either a shared uniform variable or coordinate-specific uniform variables, and each preserves FDR control under arbitrary dependence while producing at least as many rejections as e-BH. The coupling matters because e-BH uses thresholds determined by the entire evidence vector. Randomizations preserving the same coordinatewise expectations can therefore produce different rejection sets and different power.

The joint law of the randomization is thus a free parameter within the construction, and the choice among its realizations is left open. At a fixed evidence vector, a rule of this form retains the e-BH rejection set and adds a random set supported on the remaining coordinates, subject to a conditional expectation constraint for each coordinate not already rejected. Xu and Ramdas (2025) state the resulting optimization problem but do not solve it; in their conclusion they observe that no optimality has been established for any of their procedures, and they leave both the identification of an optimal scheme and the existence of an efficient algorithm open. Optimization of a discovery objective under error constraints has an established literature of its own, in which Rosset et al. (2022) characterize optimal and maximin rejection policies for specified testing models, but that tradition optimizes over the sampling distribution of the data. Here the statistical model is fixed and the data are given; the free variable is the joint law of the external randomization, and the quantity to be maximized is conditional on the observed evidence. The formulation of Xu and Ramdas (2025) does not characterize the inclusion probabilities attainable under the conditional expectation constraints, and it does not determine whether a single randomized rule can attain the pointwise maximum of those probabilities at every hypothesis simultaneously. These are distinct requirements, since a rule can maximize an aggregate discovery objective without attaining the pointwise maximum at every hypothesis. Three questions follow:

  • What limits do the conditional expectation constraints impose on the inclusion probability of each hypothesis?

  • Can a single randomized rule attain all of these limits simultaneously?

  • If such a rule exists, is its conditional rejection-set law uniquely determined?

This paper addresses these questions through a framework of conditional certification.

We associate with each realized rejection set a vector of certificates determined by its cardinality, motivated by the self-consistency property underlying e-BH (Blanchard and Roquain [3]), and require that the conditional expectation of each certificate, given the observed evidence, be bounded by the corresponding e-value. Because the requirement constrains each coordinate separately at a fixed evidence vector, any bound it implies applies to each hypothesis on its own and holds under every distribution compatible with the e-value condition. Joint rounding is one way to satisfy these constraints, but it is not the only one, and it is not the one adopted here: certification imposes them on the distribution of the rejection set directly, so the rules it admits need not be obtainable by rounding the evidence, and the class it defines is correspondingly larger than the class of joint roundings. The construction of Xu and Ramdas (2025) motivates the optimization problem. The certification framework formulates that problem over the larger class of rules it admits, and the analysis in this paper solves it explicitly.

We derive sharp upper bounds on the conditional probability that each hypothesis can be rejected under certification, and construct a single randomized procedure that attains all of them simultaneously. The rule uses one independent uniform random variable and rejects a prefix of the ordered e-values, a form that follows from the analysis rather than being imposed at the outset. Any rule maximizing a weighted sum of inclusion probabilities with strictly positive weights has the same conditional rejection-set law. The procedure therefore maximizes every nonnegative weighted sum of conditional inclusion probabilities, including the expected number of discoveries and the expected number of true discoveries under any configuration of true and false nulls, and the optimality is uniform over the certified class rather than relative to a particular competitor. We also establish a pathwise nesting: for every evidence vector and every realization of the shared uniform variable, the e-BH rejection set is contained in that of the U-eBH procedure of Xu and Ramdas (2025), which is contained in that of the proposed rule.

The optimality is relative to the class of conditionally certified rules, not to all FDR-controlling randomized procedures. Compound e-values (Ignatiadis et al., [7]) and e-value-based closure principles (Xu et al., 2025) fall outside this class, and the results do not constrain them. Within the class, the characterization is complete: the bounds are sharp, and a rule attaining them is exhibited. Numerical experiments under positive and negative dependence show that the theoretical gains translate into power improvements over the existing randomized e-BH procedures, largest at intermediate signal strengths, with attained FDR below the target throughout.

The remainder of the paper is organized as follows. § 2 introduces the testing framework and notation. § 3 develops conditional certification and establishes the bounds on rejection probabilities, and § 4 constructs the optimal procedure and proves its optimality and uniqueness properties. § 5 presents numerical comparisons with the existing e-BH procedures, and the appendix contains the technical verifications and the descriptions of the competing randomized procedures.

Setup and Notation

We consider the problem of simultaneously testing KK hypotheses using e-values under arbitrary dependence, with target false discovery rate α∈(0,1)\alpha\in(0,1). We allow the decision rules to depend on an external source of randomization independent of the evidence. We first define the evidence model and the randomized decision rules, then the performance criteria and the e-BH benchmark.

The Testing Problem and Randomized Rules

Let P\mathcal{P} be a class of distributions on a common measurable space. For each i∈[K]i \in[K], let Hi⊆PH_i \subseteq\mathcal{P} denote the ithi^{\text{th}} null hypothesis. For P∈PP \in\mathcal{P}, let N(P)={i∈[K]:P∈Hi}\mathcal{N}(P) = \{i \in[K] : P \in H_i\} denote the set of true null hypotheses, with K0(P)=∣N(P)∣K_0(P) = |\mathcal{N}(P)| true nulls and K1(P)=K−K0(P)K_1(P) = K - K_0(P) alternatives. We write Nc=[K]∖N\mathcal{N}^{c} = [K] \setminus\mathcal{N} for the complement. We observe an evidence vector X=(X1,X2,…,XK)∈[0,∞)KX = (X_1, X_2, \ldots, X_K) \in[0,\infty)^K, finite almost surely. Each coordinate is an e-value for its hypothesis, i.e.,

EP[Xi]≤1 for every P∈Hi.\mathbb{E}_{P}[X_i] \le1 \text{ for every } P \in H_i.

The coordinates may be arbitrarily dependent, and no expectation restriction is imposed on XiX_i when P∉HiP \notin H_i.

Let VV be an auxiliary random element with distribution QQ on a measurable space V\mathcal{V}, independent of XX under every P∈PP \in\mathcal{P}. A randomized rejection rule is a measurable map D:[0,∞)K×V→2[K]D : [0,\infty)^K \times\mathcal{V} \to2^{[K]}. At evidence XX, the reported rejection set is D(X,V)D(X,V). A deterministic rule is a special case in which D(x,V)D(x,V) does not depend on VV. We use PV\mathbb{P}_V and EV\mathbb{E}_V for probability and expectation over the randomization at fixed xx, and PP,V\mathbb{P}_{P,V} and EP,V\mathbb{E}_{P,V} when both the data and the randomization are integrated. The conditional inclusion probability of hypothesis ii under rule DD is

πiD(x)=PV{i∈D(x,V)}.\pi_i^D(x) = \mathbb{P}_V\{i \in D(x,V)\}.

The rejection count is RD(x,V)=∣D(x,V)∣R_D(x,V) = |D(x,V)|.

Error Control and Discovery Objectives

For a realized rejection set A⊆[K]A \subseteq[K] and a distribution P∈PP \in\mathcal{P}, the false discovery proportion is

FDP⁡P(A)=∣A∩N(P)∣∣A∣∨1.\operatorname{FDP}_P(A) = \frac{|A \cap\mathcal{N}(P)|}{|A| \vee1}.

For a randomized rule DD, the false discovery rate is FDR⁡P(D)=EP,V[FDP⁡P(D(X,V))]\operatorname{FDR}_P(D) = \mathbb{E}_{P,V}[\operatorname{FDP}_P(D(X,V))].

The rule DD is valid at level α\alpha if FDR⁡P(D)≤α\operatorname{FDR}_P(D) \le\alpha for every P∈PP \in\mathcal{P}. When K1(P)>0K_1(P) > 0, the average power of DD under PP is

Power⁡P(D)=EP,V[∣D(X,V)∩N(P)c∣]K1(P)=1K1(P)∑i∉N(P)EP[πiD(X)].\operatorname{Power}_{P}(D)=\frac{\mathbb{E}_{P,V}\left[\left|D(X,V)\cap\mathcal{N}(P)^{c}\right|\right]}{K_{1}(P)}=\frac{1}{K_{1}(P)}\sum_{i\notin\mathcal{N}(P)}\mathbb{E}_{P}\left[\pi_{i}^{D}(X)\right].

We compare conditional inclusion probabilities πiD(x)\pi_{i}^{D}(x) at fixed inputs in the following sections. Averaging over XX then yields comparisons of average power.

The e-BH Rule and Self-Consistency

For a fixed xx, we write x[1]≥x[2]≥⋯≥x[K]x_{[1]}\ge x_{[2]}\ge\cdots\ge x_{[K]} for its coordinates in decreasing order.

Define the e-BH thresholds and selected rank by

qr=Kαr,re(x)=max⁡({r∈[K]:x[r]≥qr}∪{0}).q_{r}=\frac{K}{\alpha r},\quad r_{\mathrm{e}}(x)=\max\left(\left\{r\in[K]:x_{[r]}\ge q_{r}\right\}\cup\{0\}\right).

The e-BH rejection set is

De(x)={{i∈[K]:xi≥qre(x)}re(x)>0,∅re(x)=0.(1)D_{\mathrm{e}}(x)= \begin{cases} \left\{i\in[K]:x_{i}\ge q_{r_{\mathrm{e}}(x)}\right\} & r_{\mathrm{e}}(x)>0,\\ \varnothing& r_{\mathrm{e}}(x)=0. \end{cases} \tag*{(1)}

By construction, ∣De(x)∣=re(x)\left|D_{\mathrm{e}}(x)\right|=r_{\mathrm{e}}(x). Under the e-value condition, the e-BH procedure controls the false discovery rate [13] with

FDR⁡P(De)≤αK0(P)K≤α for every P∈P.\operatorname{FDR}_{P}(D_{\mathrm{e}})\le\frac{\alpha K_{0}(P)}{K}\le\alpha\text{ for every }P\in\mathcal{P}.

Definition 2.1. A rejection set A⊆[K]A \subseteq[K] is self-consistent with respect to xx at level α\alpha if

i∈A⟹xi≥Kα(∣A∣∨1).i \in A \Longrightarrow x_i \ge\frac{K}{\alpha(|A| \lor1)}.

The empty set is self-consistent with respect to every xx.

For every xx, the e-BH rejection set De(x)D_e(x) is self-consistent with respect to xx, and every rejection set that is self-consistent with respect to xx is contained in De(x)D_e(x). The e-BH rule therefore returns the maximal self-consistent set at every input, and it is the benchmark against which the procedures developed below are measured.

Conditional Certification and Inclusion Bounds

The self-consistency condition of § 2.3 requires each rejected coordinate to clear an evidence threshold determined by the rejection count. We express this requirement through certificates and study the resulting inequalities in expectation over the external randomization. The development proceeds in three stages: we first impose the inequalities on true-null coordinates and establish FDR control, then derive a bound on conditional inclusion probabilities under that constraint, and finally introduce a condition that can be verified without identifying the true-null set.

Certificates and FDR Control

For a realized rejection set AA, define its certificate Z(A)=(Z1(A),Z2(A),…,ZK(A))Z(A) = (Z_1(A), Z_2(A), \ldots, Z_K(A)) by

Zi(A)=Kα(∣A∣∨1)1{i∈A},i∈[K].Z_i(A) = \frac{K}{\alpha(|A| \lor1)}\mathbf{1}\{i \in A\}, \quad i \in[K].

The certificate Zi(A)Z_i(A) equals K/(α∣A∣)K/(\alpha|A|) when i∈Ai \in A and zero otherwise. The self-consistency condition of Definition 2.1 is equivalent to the pointwise inequality Zi(A)≤xiZ_i(A) \le x_i for every i∈[K]i \in[K]. For i∉Ai \notin A, Zi(A)=0≤xiZ_i(A)=0 \le x_i holds automatically.

For every P∈PP \in\mathcal{P}, the false discovery proportion can be written in terms of the certificates of the true nulls. Substituting the definition of Zi(A)Z_i(A) gives

FDP⁡P(A)=∣A∩N(P)∣∣A∣∨1=αK∑i∈N(P)Kα(∣A∣∨1)1{i∈A}=αK∑i∈N(P)Zi(A).\operatorname{FDP}_{P}(A)=\frac{|A\cap\mathcal{N}(P)|}{|A|\vee1}=\frac{\alpha}{K}\sum_{i\in\mathcal{N}(P)}\frac{K}{\alpha(|A|\vee1)}1\{i\in A\}=\frac{\alpha}{K}\sum_{i\in\mathcal{N}(P)}Z_i(A).

Since only the certificates of the true nulls appear, we impose the conditional requirement on those coordinates.

Fix a set N⊆[K]\mathcal{N}\subseteq[K]. A rule DD satisfies null-only conditional certification at N\mathcal{N} if

EV[Zi(D(x,V))]≤xi,for every x∈[0,∞)K and i∈N,(2)\mathbb{E}_{V}[Z_i(D(x,V))]\le x_i,\quad\text{for every }x\in[0,\infty)^K\text{ and }i\in\mathcal{N}, \tag*{(2)}

where the expectation is over VV at fixed xx. We refer to the right-hand side xix_i as the certificate budget for coordinate ii. The certification condition (2) is stated in terms of the certificate Z(D)Z(D). We now characterize it by the existence of a nonnegative evidence vector that supports the rejection set through self-consistency and satisfies the same conditional budgets.

A measurable vector S:[0,∞)K×V→[0,∞)KS:[0,\infty)^K\times\mathcal{V}\to[0,\infty)^K supports a rule DD if D(x,V)D(x,V) is self-consistent with respect to S(x,V)S(x,V) for every fixed xx, i.e.,

i∈D(x,V)⟹Si(x,V)≥Kα(∣D(x,V)∣∨1).i\in D(x,V)\quad\Longrightarrow\quad S_i(x,V)\ge\frac{K}{\alpha(|D(x,V)|\vee1)}.

Proposition 3.1. Fix a set N⊆[K]\mathcal{N} \subseteq[K]. A rule DD satisfies (2) at N\mathcal{N} if and only if there exists a nonnegative supporting vector SS such that

EV[Si(x,V)]≤xi,for every x∈[0,∞)K and i∈N.\mathbb{E}_{V}[S_i(x,V)] \leq x_i,\quad\text{for every } x \in[0,\infty)^K \text{ and } i \in\mathcal{N}.

Proof. Suppose first that DD admits a supporting vector SS with the stated budgets. For every (x,V)(x,V) and every ii, self-consistency and nonnegativity give

Zi(D(x,V))≤Si(x,V),Z_i(D(x,V)) \leq S_i(x,V),

as Zi=0≤SiZ_i = 0 \leq S_i whenever i∉D(x,V)i \notin D(x,V), and Zi=K/(α∣D(x,V)∣)≤SiZ_i = K/(\alpha|D(x,V)|) \leq S_i whenever i∈D(x,V)i \in D(x,V). Taking expectations and applying the budget on SiS_i yields

EV[Zi(D(x,V))]≤EV[Si(x,V)]≤xi,i∈N.\mathbb{E}_{V}[Z_i(D(x,V))] \leq\mathbb{E}_{V}[S_i(x,V)] \leq x_i,\quad i \in\mathcal{N}.

Conversely, if (2) holds, take Si(x,V)=Zi(D(x,V))S_i(x,V) = Z_i(D(x,V)). The vector SS supports DD by construction, since Si(x,V)=K/(α∣D(x,V)∣)S_i(x,V) = K/(\alpha|D(x,V)|) on the rejection set, and the inequalities EV[Si(x,V)]≤xi\mathbb{E}_{V}[S_i(x,V)] \leq x_i required by the proposition are exactly (2).

The certificate is the coordinatewise smallest nonnegative vector supporting a given rejection set. Imposing conditional budgets on Z(D)Z(D) is therefore equivalent to requiring the existence of supporting evidence satisfying those budgets.

Proposition 3.2. Fix P∈PP \in\mathcal{P}. If a rule DD satisfies (2) at N(P)\mathcal{N}(P), then FDR⁡P(D)≤αK0(P)/K≤α\operatorname{FDR}_{P}(D) \leq\alpha K_0(P)/K \leq\alpha.

Proof. By the certificate representation of the false discovery proportion and iterated

expectation, we have

FDR⁡P(D)=αK∑i∈N(P)EP,V[Zi(D(X,V))]=αK∑i∈N(P)EP[EV[Zi(D(X,V))]]≤αK∑i∈N(P)EP[Xi]≤αK0(P)K.\operatorname{FDR}_{P}(D) = \frac{\alpha}{K} \sum_{i \in\mathcal{N}(P)} \mathbb{E}_{P,V}[Z_i(D(X,V))] = \frac{\alpha}{K} \sum_{i \in\mathcal{N}(P)} \mathbb{E}_{P}\left[\mathbb{E}_{V}[Z_i(D(X,V))]\right] \le\frac{\alpha}{K} \sum_{i \in\mathcal{N}(P)} \mathbb{E}_{P}[X_i] \le\frac{\alpha K_0(P)}{K}.

Null-only conditional certification is sufficient for FDR control. We now derive the inclusion bound that this condition implies.

An Oracle Inclusion Bound

Fix a deterministic input x∈[0,∞)Kx \in[0,\infty)^K, a set N⊆[K]\mathcal{N} \subseteq[K], and a rule DD satisfying (2) at N\mathcal{N}. We ask what these inequalities imply for the conditional inclusion probability πiD(x)=PV{i∈D(x,V)}\pi_i^D(x) = \mathbb{P}_{V}\{i \in D(x,V)\}. The calculation is pointwise in xx and requires no distributional assumptions on the evidence. The starting point is a certificate identity that expresses the selection of a coordinate through its certificate and the certificates of the remaining coordinates. For every realized set AA and every coordinate ii, we have

1{i∈A}=αK∑j=1Kmin⁡{Zi(A),Zj(A)}.(3)\mathbf{1}\{i \in A\} = \frac{\alpha}{K}\sum_{j=1}^{K}\min\{Z_i(A), Z_j(A)\}. \tag*{(3)}

To see this, if i∉Ai \notin A, then Zi(A)=0Z_i(A) = 0, so every term in the sum vanishes and both sides equal 0. If i∈Ai \in A, then Zi(A)=K/(α∣A∣)Z_i(A) = K/(\alpha|A|). The terms with j∈Aj \in A equal K/(α∣A∣)K/(\alpha|A|), and the terms with j∉Aj \notin A vanish. Since there are ∣A∣|A| terms of the first kind, the sum equals K/αK/\alpha, and multiplying by α/K\alpha/K gives 1. We now apply (3) to bound the conditional inclusion probability of a constrained coordinate.

Proposition 3.3. Let DD satisfy (2) at N\mathcal{N}, and let K1=K−∣N∣K_1 = K - \lvert\mathcal{N}\rvert. Then for every x∈[0,∞)Kx \in[0,\infty)^K and every i∈Ni \in\mathcal{N},

πiD(x)≤1∧αK[K1xi+∑j∈Nmin⁡(xi,xj)].\pi_i^D(x) \le1 \wedge\frac{\alpha}{K}\left[K_1x_i+\sum_{j\in\mathcal{N}}\min(x_i,x_j)\right].

Proof. Fix i∈Ni \in\mathcal{N}. Taking expectations in (3) with A=D(x,V)A = D(x,V) and writing Zj=Zj(D(x,V))Z_j = Z_j(D(x,V)) gives

πiD(x)=αK[∑j∈NEV[min⁡(Zi,Zj)]+∑j∉NEV[min⁡(Zi,Zj)]].\pi_i^D(x)=\frac{\alpha}{K}\left[\sum_{j\in\mathcal{N}}\mathbb{E}_V[\min(Z_i,Z_j)]+\sum_{j\notin\mathcal{N}}\mathbb{E}_V[\min(Z_i,Z_j)]\right].

For j∈Nj \in\mathcal{N}, both certificates satisfy (2), and since the minimum is bounded above by either argument,

EV[min⁡(Zi,Zj)]≤min⁡{EV[Zi],EV[Zj]}≤min⁡(xi,xj).\mathbb{E}_V[\min(Z_i,Z_j)]\le\min\{\mathbb{E}_V[Z_i],\mathbb{E}_V[Z_j]\}\le\min(x_i,x_j).

For j∉Nj \notin\mathcal{N}, only the certificate of ii is constrained, so

EV[min⁡(Zi,Zj)]≤EV[Zi]≤xi.\mathbb{E}_V[\min(Z_i,Z_j)]\le\mathbb{E}_V[Z_i]\le x_i.

There are K1=K−∣N∣K_1=K-\lvert\mathcal{N}\rvert coordinates with j∉Nj\notin\mathcal{N}. Substituting these bounds gives

πiD(x)≤αK[∑j∈Nmin⁡(xi,xj)+K1xi].\pi_i^D(x)\le\frac{\alpha}{K}\left[\sum_{j\in\mathcal{N}}\min(x_i,x_j)+K_1x_i\right].

Combining with the elementary bound πiD(x)≤1\pi_i^D(x)\le1 gives the stated inequality.

This is an oracle bound: it depends on the true configuration through N\mathcal{N} and K1K_1. The argument requires i∈Ni \in\mathcal{N}, since it uses the certificate budget for coordinate ii; for i∉Ni \notin\mathcal{N}, null-only certification gives no improvement over the elementary bound πiD(x)≤1\pi_i^D(x) \le1. Since N\mathcal{N} is unknown, we next impose the certification condition on every coordinate.

Certification on All Coordinates

We impose the certificate condition on every coordinate and refer to the resulting rules as conditionally certified. The following sections study optimality within this class.

Definition 3.1. The conditionally certified class C\mathcal{C} consists of all randomized rules DD satisfying

EV[Zi(D(x,V))]≤xi,for every x∈[0,∞)K and every i∈[K].(4)\mathbb{E}_V[Z_i(D(x,V))] \le x_i,\quad\text{for every }x \in[0,\infty)^K\text{ and every }i \in[K]. \tag*{(4)}

Every D∈CD \in\mathcal{C} satisfies FDR⁡P(D)≤αK0(P)/K\operatorname{FDR}_{P}(D) \le\alpha K_0(P)/K for every P∈PP \in\mathcal{P}, by Proposition 3.2 applied with N=N(P)\mathcal{N} = \mathcal{N}(P). By Proposition 3.1 applied with N=[K]\mathcal{N} = [K], a rule DD belongs to C\mathcal{C} if and only if it admits a nonnegative supporting vector SS with

EV[Si(x,V)]≤xi,for every x∈[0,∞)K and every i∈[K].\mathbb{E}_V[S_i(x,V)] \le x_i,\quad\text{for every }x \in[0,\infty)^K\text{ and every }i \in[K].

If SS satisfies the inequalities and D(x,V)=De(S(x,V))D(x,V) = D_{\mathrm{e}}(S(x,V)), then D∈CD \in\mathcal{C}, since e-BH is self-consistent with respect to its input. For an arbitrary supporting vector, self-consistency only implies D(x,V)⊆De(S(x,V))D(x,V) \subseteq D_{\mathrm{e}}(S(x,V)).

The ordinary e-BH rule belongs to C\mathcal{C}: its self-consistency gives the pointwise inequalities Zi(De(x))≤xiZ_i(D_{\mathrm{e}}(x)) \le x_i for every ii, which imply (4) after taking expectations. Detailed

::: membership arguments for the procedures of Xu and Ramdas (2025) are deferred to the Appendix.

Applying Proposition 3.3 with N=[K]\mathcal{N} = [K] gives, for every D∈CD \in\mathcal{C}, every x∈[0,∞)Kx \in[0,\infty)^K, and every i∈[K]i \in[K], πiD(x)≤1∧Gi(x)\pi_i^D(x) \le1 \wedge G_i(x), where

Gi(x)=αK∑j=1Kmin⁡(xi,xj).G_i(x) = \frac{\alpha}{K} \sum_{j=1}^{K} \min(x_i,x_j).

Optimality under Conditional Certification

Section 3.3 established that every D∈CD \in\mathcal{C} satisfies the coordinatewise bound

πiD(x)≤1∧Gi(x),Gi(x)=αK∑j=1Kmin⁡(xi,xj),\pi_i^D(x) \le1 \wedge G_i(x), \quad G_i(x) = \frac{\alpha}{K} \sum_{j=1}^{K} \min(x_i,x_j),

for every x∈[0,∞)Kx \in[0,\infty)^K and every i∈[K]i \in[K]. This section constructs a single rule in C\mathcal{C} that attains all of these bounds simultaneously, establishes simultaneous optimality and uniqueness of its conditional law, and compares it with e-BH and the randomized procedure U-eBH of Xu and Ramdas (2025).

We begin by defining the candidate rule. Let U∼Uniform⁡(0,1)U \sim\operatorname{Uniform}(0,1) be independent of XX, and define

D⋆(x,U)={i∈[K]:U≤Gi(x)}.D^\star(x,U) = \{i \in[K] : U \le G_i(x)\}.

With a single uniform variable UU independent of XX, write πi⋆(x)=PU{i∈D⋆(x,U)}\pi_i^\star(x) = \mathbb{P}_U\{i \in D^\star(x,U)\} for the conditional inclusion probability. Because UU is uniform on (0,1)(0,1), πi⋆(x)=1∧Gi(x)\pi_i^\star(x) = 1 \wedge G_i(x). Attaining these bounds does not by itself place D⋆D^\star in C\mathcal{C}; certification is verified in Theorem 4.1.

The score Gi(x)G_i(x) is monotone in xix_i. If xi≥xjx_i \ge x_j, then min⁡(xi,xℓ)≥min⁡(xj,xℓ)\min(x_i,x_\ell) \ge\min(x_j,x_\ell) for every ℓ\ell, so Gi(x)≥Gj(x)G_i(x) \ge G_j(x). The rule therefore selects a prefix of the evidence ordering, and tied inputs are selected together. Zero inputs are never selected, as Gi(x)=0G_i(x)=0 whenever xi=0x_i=0. Because D⋆D^\star selects a prefix, it is convenient to describe it through the ordered coordinates.

For x[1]≥x[2]≥⋯≥x[K]x_{[1]} \ge x_{[2]} \ge\cdots\ge x_{[K]}, define the ordered thresholds

gr=αK(rx[r]+∑j=r+1Kx[j]),r∈[K],g_r=\frac{\alpha}{K}\left(rx_{[r]}+\sum_{j=r+1}^{K}x_{[j]}\right),\quad r\in[K],

and the rejection count

R⋆(x,U)=max⁡({r∈[K]:U≤gr}∪{0}).R^\star(x,U)=\max\left(\{r\in[K]:U\le g_r\}\cup\{0\}\right).

The coordinate at rank rr satisfies G[r](x)=grG_{[r]}(x)=g_r: the terms with j≤rj\le r contribute x[r]x_{[r]} each, and the terms with j>rj>r contribute x[j]x_{[j]}. The thresholds satisfy g1≥g2≥⋯≥gK≥0g_1\ge g_2\ge\cdots\ge g_K\ge0; the nonnegativity is immediate from x[j]≥0x_{[j]}\ge0, and the monotonicity is verified as part of the proof of Theorem 4.1. The set D⋆(x,U)D^\star(x,U) therefore consists of the coordinates at ranks up to R⋆(x,U)R^\star(x,U). We now show that D⋆D^\star is conditionally certified.

Theorem 4.1. Let U∼Uniform⁡(0,1)U\sim\operatorname{Uniform}(0,1). For every x∈[0,∞)Kx\in[0,\infty)^K and every i∈[K]i\in[K],

EU[Zi(D⋆(x,U))]≤xi.\mathbb{E}_U[Z_i(D^\star(x,U))]\le x_i.

Consequently D⋆∈CD^\star\in\mathcal{C}, and Proposition 3.2 gives FDR⁡P(D⋆)≤αK0(P)/K\operatorname{FDR}_{\mathcal{P}}(D^\star)\le\alpha K_0(\mathcal{P})/K for every P∈PP\in\mathcal{P}.

Proof. Both D⋆D^\star and the certificate Z(D⋆)Z(D^\star) are equivariant under relabeling of the coordinates, so it suffices to prove the claim for a sorted input x1≥x2≥⋯≥xKx_1\ge x_2\ge\cdots\ge x_K and then extend by relabeling at the end. Fix i∈[K]i\in[K] in this ordering. Set xK+1=0x_{K+1}=0, gK+1=0g_{K+1}=0, and hr=1∧grh_r=1 \wedge g_r for r=1,2,…,K+1r=1,2,\ldots,K+1. Using the definition of grg_r, we write

gr−gr+1=αrK(xr−xr+1)≥0,r=1,2,…,K.g_r-g_{r+1}=\frac{\alpha r}{K}(x_r-x_{r+1})\geq0,\quad r=1,2,\ldots,K.

Thus, g1≥g2≥…≥gK≥0g_1\geq g_2\geq\ldots\geq g_K\geq0 and h1≥h2≥…≥hK≥0h_1\geq h_2\geq\ldots\geq h_K\geq0. For r=1,2,…,Kr=1,2,\ldots,K define the intervals Ir=(hr+1,hr]I_r=(h_{r+1},h_r]. The intervals are disjoint with union (0,h1]⊆(0,1](0,h_1]\subseteq(0,1], since hr≤1h_r\leq1 for every rr.

We claim that R⋆(x,U)=rR^{\star}(x,U)=r if and only if U∈IrU\in I_r. Suppose first that U∈IrU\in I_r, so that hr+1<U≤hrh_{r+1}<U\leq h_r. Since hr≤grh_r\leq g_r, we have U≤grU\leq g_r and therefore R⋆≥rR^{\star}\geq r. To show that rank r+1r+1 fails, note that U>hr+1U>h_{r+1}. If gr+1>1g_{r+1}>1, then hr+1=1h_{r+1}=1, which contradicts U≤1U\leq1; hence gr+1≤1g_{r+1}\leq1, so hr+1=gr+1h_{r+1}=g_{r+1} and U>gr+1U>g_{r+1}. Since rank r+1r+1 fails the condition U≤gr+1U\leq g_{r+1}, we have R⋆<r+1R^{\star}<r+1, and combined with R⋆≥rR^{\star}\geq r this gives R⋆=rR^{\star}=r.

Conversely, suppose R⋆=rR^{\star}=r with r≥1r\geq1, so that U≤grU\leq g_r and U>gr+1U>g_{r+1}. From U>gr+1U>g_{r+1} and U≤1U\leq1 we obtain gr+1<1g_{r+1}<1, hence hr+1=gr+1<Uh_{r+1}=g_{r+1}<U. For the upper endpoint, if gr≤1g_r\leq1, then hr=gr≥Uh_r=g_r\geq U, and if gr>1g_r>1, then hr=1≥Uh_r=1\geq U; in either case U≤hrU\leq h_r. Together with U>hr+1U>h_{r+1} this gives U∈IrU\in I_r. The case R⋆=0R^{\star}=0 occurs if and only if U>g1U>g_1, which is equivalent to U>h1U>h_1 because h1=1∧g1h_1=1\wedge g_1 and U≤1U\leq1. Therefore

PU(R⋆(x,U)=r)=hr−hr+1,r=1,2,…,K,\mathbb{P}_U(R^{\star}(x,U)=r)=h_r-h_{r+1},\quad r=1,2,\ldots,K,

and

PU(R⋆(x,U)=0)=1−h1.\mathbb{P}_U(R^{\star}(x,U)=0)=1-h_1.

Returning to the fixed coordinate i∈[K]i\in[K], we now compute its certificate expectation.

For r≥ir\geq i, on the event {R⋆(x,U)=r}\{R^{\star}(x,U)=r\}, the coordinate at rank ii belongs to D⋆(x,U)D^{\star}(x,U), so its certificate equals Zi(D⋆(x,U))=K/(αr)Z_i(D^\star(x,U))=K/(\alpha r). Consequently,

EU[Zi(D⋆(x,U))]=∑r=iKKαrPU(R⋆(x,U)=r)=∑r=iKKαr(hr−hr+1).\mathbb{E}_U[Z_i(D^\star(x,U))]=\sum_{r=i}^{K}\frac{K}{\alpha r}\mathbb{P}_U(R^\star(x,U)=r)=\sum_{r=i}^{K}\frac{K}{\alpha r}(h_r-h_{r+1}).

Since gr≥gr+1g_r\ge g_{r+1} and clipping at one cannot increase a gap, 0≤hr−hr+1≤gr−gr+10\le h_r-h_{r+1}\le g_r-g_{r+1}.

Substituting these bounds into the sum above gives

EU[Zi(D⋆(x,U))]≤∑r=iK(xr−xr+1)=xi−xK+1=xi.\mathbb{E}_U[Z_i(D^\star(x,U))]\le\sum_{r=i}^{K}(x_r-x_{r+1})=x_i-x_{K+1}=x_i.

For an arbitrary input xx, let σ\sigma be the permutation that sorts xx in decreasing order, so xiσ=xσ(i)=x[i]x_i^\sigma=x_{\sigma(i)}=x_{[i]}. The score Gi(⋅)G_i(\cdot), the rule D⋆D^\star, and the certificate Zi(D⋆)Z_i(D^\star) are equivariant under relabeling, so the inequality proved for the sorted input transfers to xx. Hence

EU[Zi(D⋆(x,U))]≤xi\mathbb{E}_U[Z_i(D^\star(x,U))]\le x_i

for every i∈[K]i\in[K]. Therefore D⋆∈CD^\star\in\mathcal{C}, and the FDR bound is a direct consequence of Proposition 3.2.

Combining the coordinatewise bound of § 3.3 with Theorem 4.1 gives simultaneous optimality.

Corollary 4.1. For every D∈CD\in\mathcal{C}, every x∈[0,∞)Kx\in[0,\infty)^K, and every i∈[K]i\in[K],

πiD(x)≤πi⋆(x)=1∧Gi(x).\pi_i^D(x)\le\pi_i^\star(x)=1\wedge G_i(x).

Proof. § 3.3 gives πiD(x)≤1∧Gi(x)\pi_i^D(x)\le1\wedge G_i(x) for every D∈CD\in\mathcal{C}. Theorem 4.1 gives D⋆∈CD^\star\in\mathcal{C}, and since πi⋆(x)=1∧Gi(x)\pi_i^\star(x)=1\wedge G_i(x) by construction of D⋆D^\star, the claim follows.

Corollary 4.1 implies that every D∈CD\in\mathcal{C} attains at most the marginal inclusion probabilities of D⋆(x,U)D^\star(x,U) at this input. We now extend this to arbitrary weighted sums and show that any rule attaining the maximum with strictly positive weights has the same conditional law as D⋆(x,U)D^\star(x,U). We first record two consequences of equality in the marginal bounds.

The following lemma records the equality conditions in the certificate bound.

Lemma 1. Let DD satisfy EV[Zi(D)]≤xi\mathbb{E}_V[Z_i(D)] \le x_i for every i∈[K]i \in[K]. If πiD(x)=Gi(x)≤1\pi_i^D(x) = G_i(x) \le1 for some i∈[K]i \in[K], then EV[Zi(D)]=xi\mathbb{E}_V[Z_i(D)] = x_i and EV[min⁡(Zi(D),Zj(D))]=min⁡(xi,xj)\mathbb{E}_V[\min(Z_i(D), Z_j(D))] = \min(x_i,x_j) for every j∈[K]j \in[K].

Proof. By the certificate identity and the certificate budget,

πiD(x)=αK∑j=1KEV[min⁡(Zi(D),Zj(D))]≤αK∑j=1Kmin⁡(xi,xj)=Gi(x).\pi_i^D(x) = \frac{\alpha}{K} \sum_{j=1}^{K} \mathbb{E}_V[\min(Z_i(D),Z_j(D))] \le\frac{\alpha}{K} \sum_{j=1}^{K} \min(x_i,x_j) = G_i(x).

Since the two ends are equal, every term in the sum is tight, and the claim follows. □

Lemma 2. Fix x∈[0,∞)Kx \in[0,\infty)^K. Let DD satisfy EV[Zi(D)]≤xi\mathbb{E}_V[Z_i(D)] \le x_i and πiD(x)=1∧Gi(x)\pi_i^D(x) = 1 \wedge G_i(x) for every i∈[K]i \in[K]. Then DD is almost surely a prefix of the evidence ordering, i.e.,

j∈D and xi≥xj⟹i∈D almost surely.j \in D \text{ and } x_i \ge x_j \Longrightarrow i \in D \text{ almost surely}.

Proof. A coordinate with Gi(x)>1G_i(x) > 1 satisfies πiD(x)=1\pi_i^D(x) = 1 and is selected almost surely. A coordinate with Gi(x)≤1G_i(x) \le1 satisfies Lemma 1.

Fix j∈[K]j \in[K] and suppose j∈Dj \in D. If Gj(x)>1G_j(x) > 1, then jj is selected almost surely. For any ii with xi≥xjx_i \ge x_j, monotonicity of GG gives Gi(x)≥Gj(x)>1G_i(x) \ge G_j(x) > 1, so ii is also selected almost surely.

If Gj(x)≤1G_j(x) \le1, Lemma 1 applied to jj gives EV[Zj(D)]=xj\mathbb{E}_V[Z_j(D)] = x_j and EV[min⁡(Zj(D),Zi(D))]=min⁡(xj,xi)\mathbb{E}_V[\min(Z_j(D),Z_i(D))] = \min(x_j,x_i). For ii with xi≥xjx_i \ge x_j, we have min⁡(xj,xi)=xj=EV[Zj(D)]\min(x_j,x_i) = x_j = \mathbb{E}_V[Z_j(D)], so EV[min⁡(Zj(D),Zi(D))]=EV[Zj(D)]\mathbb{E}_{V}[\min(Z_j(D), Z_i(D))] = \mathbb{E}_{V}[Z_j(D)]. Since min⁡(Zj(D),Zi(D))≤Zj(D)\min(Z_j(D), Z_i(D)) \le Z_j(D) pointwise, the difference is nonnegative with zero expectation, hence zero almost surely. Therefore Zj(D)≤Zi(D)Z_j(D) \le Z_i(D) almost surely. On the event {j∈D}\{j \in D\}, we have Zj(D)=K/(α∣D∣)>0Z_j(D) = K/(\alpha|D|) > 0 whenever ∣D∣>0|D| > 0, so Zi(D)≥Zj(D)>0Z_i(D) \ge Z_j(D) > 0 and therefore i∈Di \in D. If ∣D∣=0|D| = 0, the case is vacuous.

Equal positive inputs satisfy Gi(x)=Gj(x)G_i(x) = G_j(x). If this common value is at least 1, both are selected almost surely; otherwise, applying the argument above in both directions gives i∈D⟺j∈Di \in D \Longleftrightarrow j \in D almost surely. Zero inputs have Gi(x)=0G_i(x) = 0 and are never selected. Therefore DD is almost surely a prefix of the evidence ordering.

Theorem 4.2. Fix x∈[0,∞)Kx \in[0,\infty)^K and w=(w1,w2,…,wK)∈[0,∞)Kw = (w_1,w_2,\ldots,w_K) \in[0,\infty)^K. For every random rejection set DD with EV[Zi(D)]≤xi\mathbb{E}_{V}[Z_i(D)] \le x_i for every i∈[K]i \in[K],

∑i=1KwiPV(i∈D)≤∑i=1Kwiπi⋆(x).(5)\sum_{i=1}^{K} w_i \mathbb{P}_{V}(i \in D) \le\sum_{i=1}^{K} w_i \pi_i^\star(x). \tag*{(5)}

Moreover, if wi>0w_i > 0 for every ii and equality holds, then DD has the same conditional distribution as D⋆D^\star at xx.

Proof. By the oracle bound of § 3.2 applied with N=[K]\mathcal{N} = [K],

PV(i∈D)≤1∧Gi(x)=πi⋆(x),\mathbb{P}_{V}(i \in D) \le1 \wedge G_i(x) = \pi_i^\star(x),

for every i∈[K]i \in[K]. Multiplying by wi≥0w_i \ge0 and summing over ii gives the stated inequality.

For the uniqueness claim, suppose wi>0w_i > 0 for every i∈[K]i \in[K] and equality holds in (5).

Every term wiPV(i∈D)w_i\mathbb{P}_{V}(i \in D) is at most wiπi⋆(x)w_i\pi_i^\star(x), which implies

PV(i∈D)=πi⋆(x)=1∧Gi(x),\mathbb{P}_{V}(i \in D) = \pi_i^\star(x) = 1 \wedge G_i(x),

for every i∈[K]i \in[K]. By Lemma 2, DD is almost surely a prefix of the evidence ordering.

Write σx(r)\sigma_x(r) for the coordinate at rank rr, so that xσx(1)≥xσx(2)≥⋯≥xσx(K)x_{\sigma_x(1)} \ge x_{\sigma_x(2)} \ge\cdots\ge x_{\sigma_x(K)}, and set hr=1∧grh_r = 1 \wedge g_r for r∈[K]r \in[K], as in the proof of Theorem 4.1. For a prefix rule, σx(r)∈D\sigma_x(r) \in D if and only if the rejection count R=∣D∣≥rR = |D| \ge r, so

P(R≥r)=PV(σx(r)∈D)=1∧Gσx(r)(x)=hr,r=1,2,…,K.\mathbb{P}(R \ge r) = \mathbb{P}_{V}(\sigma_x(r) \in D) = 1 \wedge G_{\sigma_x(r)}(x) = h_r,\quad r = 1,2,\ldots,K.

DD is almost surely a prefix of the evidence ordering, i.e., DD is determined by RR. The tail probabilities P(R≥r)\mathbb{P}(R \ge r) determine the distribution of RR and therefore determine the distribution of DD. The rule D⋆D^\star is a prefix rule with the same tails, so DD and D⋆D^\star have the same distribution at input xx.

Corollary 4.2. For every P∈PP \in\mathcal{P}, every weight vector w(X)=(w1(X),w2(X),…,wK(X))w(X) = (w_1(X), w_2(X), \ldots, w_K(X)) with wi(X)≥0w_i(X) \ge0 measurable for every i∈[K]i \in[K], and every D∈CD \in\mathcal{C},

EP[∑i=1Kwi(X)1{i∈D(X,V)}]≤EP[∑i=1Kwi(X)1{i∈D⋆(X,U)}].\mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)1\{i \in D(X,V)\}\right] \le\mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)1\{i \in D^\star(X,U)\}\right].

Proof. Fix P∈PP \in\mathcal{P} and D∈CD \in\mathcal{C}. At each input xx, Theorem 4.2 applied with the weight vector w(x)w(x) gives

∑i=1Kwi(x)πiD(x)≤∑i=1Kwi(x)πi⋆(x).\sum_{i=1}^{K} w_i(x)\pi_i^D(x) \le\sum_{i=1}^{K} w_i(x)\pi_i^\star(x).

Taking expectations over X∼PX \sim P we get:

EP[∑i=1Kwi(X)1{i∈D(X,V)}]=EP[∑i=1Kwi(X)πiD(X)]≤EP[∑i=1Kwi(X)πi⋆(X)]=EP[∑i=1Kwi(X)1{i∈D⋆(X,U)}].\begin{aligned} \mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)1\{i \in D(X,V)\}\right] &= \mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)\pi_i^D(X)\right] \\ &\le\mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)\pi_i^\star(X)\right] \\ &= \mathbb{E}_{P}\left[\sum_{i=1}^{K} w_i(X)1\{i \in D^\star(X,U)\}\right]. \end{aligned}

Corollary 4.2 yields optimality for multiple objectives. With wi(X)=1w_i(X) = 1, it gives optimality for the expected number of rejections. With wi(X)=1{i∉N(P)}w_i(X) = 1\{i \notin\mathcal{N}(P)\}, it gives optimality for the expected number of true discoveries under any truth configuration; dividing by K1(P)K_1(P) extends this to average power when K1(P)>0K_1(P) > 0.

Corollary 4.2 establishes optimality of expected weighted counts. The comparison that follows is pathwise and holds for e-BH and U-eBH under a shared uniform seed.

Given xx, draw U∼Uniform⁡(0,1)U \sim\operatorname{Uniform}(0,1) and sort xx in decreasing order. The sample D⋆(x,U)D^\star(x,U) is obtained by computing the thresholds grg_r and returning the prefix of length R⋆(x,U)R^\star(x,U).

The U-eBH rule of Xu and Ramdas (2025) applies e-BH to the scaled inputs xi/Ux_i/U for a uniform UU independent of XX. Its rejection count is

rU(x,U)=max⁡({r∈[K]:U≤αrKx[r]}∪{0}),r_U(x,U) = \max\left(\left\{r \in[K] : U \le\frac{\alpha r}{K}x_{[r]}\right\} \cup\{0\}\right),

and the rejection set DU(x,U)D_U(x,U) consists of the coordinates at ranks up to rU(x,U)r_U(x,U). We use the same uniform seed UU for comparison.

Proposition 4.1. For every x∈[0,∞)Kx \in[0,\infty)^K and every U∈(0,1)U \in(0,1),

De(x)⊆DU(x,U)⊆D⋆(x,U).D_{\mathrm{e}}(x) \subseteq D_U(x,U) \subseteq D^\star(x,U).

Proof. Let re=re(x)r_{\mathrm{e}}=r_{\mathrm{e}}(x) denote the rejection rank of e-BH. If re=0r_{\mathrm{e}}=0 then the first inclusion above is trivial. Otherwise, by definition of rer_{\mathrm{e}}, x[re]≥K/(αre)x_{[r_{\mathrm{e}}]} \ge K/(\alpha r_{\mathrm{e}}), so (αre/K)x[re]≥1>U(\alpha r_{\mathrm{e}}/K)x_{[r_{\mathrm{e}}]} \ge1 > U. Hence rank rer_{\mathrm{e}} satisfies the U-eBH condition, which implies rU≥rer_U \ge r_{\mathrm{e}} and therefore De(x)⊆DU(x,U)D_{\mathrm{e}}(x) \subseteq D_U(x,U).

For the second inclusion, if rank rr satisfies U≤(αr/K)x[r]U \le(\alpha r/K)x_{[r]}, then

gr=αK(rx[r]+∑j=r+1Kx[j])≥αrKx[r]≥U.g_r = \frac{\alpha}{K}\left(rx_{[r]}+\sum_{j=r+1}^{K}x_{[j]}\right) \ge\frac{\alpha r}{K}x_{[r]} \ge U.

This implies R⋆≥rUR^\star\ge r_U and DU(x,U)⊆D⋆(x,U)D_U(x,U) \subseteq D^\star(x,U).

Since gi≥(αr/K)x[r]g_i \ge(\alpha r/K)x_{[r]} for every r≥ir \ge i, the inclusion probability of D⋆D^\star at rank ii is at least that of DUD_U, i.e.,

PU(σx(i)∈D⋆(x,U))−PU(σx(i)∈DU(x,U))=(1∧gi)−(1∧ai(x))≥0,\mathbb{P}_U\left(\sigma_x(i) \in D^\star(x,U)\right)-\mathbb{P}_U\left(\sigma_x(i) \in D_U(x,U)\right)=(1\wedge g_i)-(1\wedge a_i(x))\ge0,

where ai(x)=max⁡r≥i(αr/K)x[r]a_i(x)=\max_{r\ge i}(\alpha r/K)x_{[r]}.

Simulations

This section reports a simulation study comparing the proposed rule with e-BH and with the competing randomized procedures. The goals are to measure the power improvement across signal strengths and dependence settings, and to verify that the attained FDR of every procedure remains below its theoretical bound.

Simulation Setup

We consider a Gaussian mean problem with K=100K = 100 hypotheses and target FDR α=0.05\alpha= 0.05. In each replication an alternative set A\mathcal{A} is drawn uniformly among the subsets of size K1=30K_1 = 30, independently of the noise, and the evidence is generated conditionally as

Z∣A∼NK(θ(A),Σ),θi(A)=μ1{i∈A}.Z \mid\mathcal{A} \sim N_K\left(\theta(\mathcal{A}), \Sigma\right), \quad\theta_i(\mathcal{A}) = \mu1\{i \in\mathcal{A}\}.

The hypotheses are Hi:θi≤0H_i: \theta_i \le0 against θi>0\theta_i > 0. True nulls have θi=0\theta_i = 0, at the boundary of the null hypothesis, and every alternative carries the same mean μ>0\mu> 0.

The covariance matrix Σ\Sigma takes one of two forms:

Σij={ρ∣i−j∣,Positive Toeplitz Dependence,1,Negative Equicorrelation, i=j,−ρ/(K−1),Negative Equicorrelation, i≠j.\Sigma_{ij} = \begin{cases} \rho^{|i-j|}, & \text{Positive Toeplitz Dependence},\\ 1, & \text{Negative Equicorrelation},\ i=j,\\ -\rho/(K-1), & \text{Negative Equicorrelation},\ i\ne j. \end{cases}

The parameter ρ\rho has different interpretations in the two cases: it is the adjacent-coordinate correlation in the Toeplitz family, and it controls the magnitude of the negative off-diagonal entries in the equicorrelation family. The signal strength μ\mu takes equally spaced values on [1,4][1, 4] in increments of 0.20.2, and the dependence parameter ρ\rho takes equally spaced values on [0,0.9][0, 0.9] in increments of 0.10.1. Each setting is evaluated over N=5000N = 5000 Monte Carlo replications. The evidence supplied to the procedures is

Xi=exp⁡(λZi−λ22),λ=2log⁡(K2α).X_i = \exp\left(\lambda Z_i - \frac{\lambda^2}{2}\right), \quad\lambda= \sqrt{2\log\left(\frac{K}{2\alpha}\right)}.

The tuning parameter λ\lambda is held fixed across the signal-strength grid, so the evidence construction is identical at every μ\mu.

Seven e-value procedures are compared:

  • e-BH, the benchmark of § 2.3,

  • R1-eBH, R2-eBH, and R-eBH, the three rounding procedures,

  • U-eBH and J-eBH, the shared-uniform and coordinate-specific randomizations,

  • D⋆D^\star, the procedure developed in § 4.

The five randomized competitors are from Xu and Ramdas (2025); their complete specifications are given in the appendix.

U-eBH and D⋆D^\star share a single uniform UU, which realizes the coupling DU(x,u)⊆D⋆(x,u)D_U(x,u) \subseteq D^\star(x,u) of Proposition 4.1 for every xx and uu. The coordinatewise uniforms used by R1-eBH, R2-eBH, R-eBH, and J-eBH are independent across hypotheses, and the two stages of R-eBH use independent randomness.

Let X(b)X^{(b)} denote the evidence and VbV_b the randomization in replication bb, let Ab\mathcal{A}_b be the alternative set in that replication, and let Nb=[K]∖Ab\mathcal{N}_b = [K] \setminus\mathcal{A}_b. The realized false discovery proportion and true-discovery proportion of a rule DD are

FbD=∣D(X(b),Vb)∩Nb∣∣D(X(b),Vb)∣∨1,TbD=∣D(X(b),Vb)∩Ab∣K1.F_b^D = \frac{\lvert D(X^{(b)}, V_b) \cap\mathcal{N}_b\rvert}{\lvert D(X^{(b)}, V_b)\rvert\vee1}, \qquad T_b^D = \frac{\lvert D(X^{(b)}, V_b) \cap\mathcal{A}_b\rvert}{K_1}.

The reported FDR and power are the averages F^D=N−1∑b=1NFbD\widehat{F}^D = N^{-1}\sum_{b=1}^{N} F_b^D and T^D=N−1∑b=1NTbD\widehat{T}^D = N^{-1}\sum_{b=1}^{N} T_b^D. Pointwise intervals use ξ^±1.96sξ/N\widehat{\xi} \pm1.96s_{\xi}/\sqrt{N}, where ξ^\widehat{\xi} and sξs_{\xi} are the sample mean and standard deviation of the corresponding replication-level quantity and sξ/Ns_{\xi}/\sqrt{N} is the Monte Carlo standard error. For D⋆D^\star against a competitor DD, the reported difference is the replication-level average of δb=TbD⋆−TbD\delta_b = T_b^{D^\star} - T_b^D, with standard error computed from the δb\delta_b. Differences and their intervals are reported in percentage points.

Simulation Results

Figure 1 reports power and FDR against μ\mu at three representative dependence settings.

Figure 1. Power (top row) and FDR (bottom row) against μ\mu at independence (ρ=0\rho= 0), positive Toeplitz dependence (ρ=0.6\rho= 0.6), and negative equicorrelation (ρ=0.9\rho= 0.9). Each panel compares the seven e-value procedures. Ribbons are pointwise 95% Monte Carlo intervals. The dashed line in the lower panels marks the reference bound αK0/K=0.035\alpha K_0/K = 0.035.

Across the full grid, D⋆D^\star attains the highest estimated power at every setting. The smallest gap over the grid is 0.03 percentage points, attained against J-eBH at the extremes of the signal-strength grid, where every procedure is near zero power or near saturation. The largest is 16.4 percentage points, attained against e-BH at intermediate signal strengths.

The dominance of D⋆D^\star over each competitor follows from the optimality theorem of § 4. The simulation quantifies the magnitude of the gaps, their concentration in the (μ,ρ)(\mu,\rho) grid, and the ordering among the competitors.

Power increases with μ\mu for every procedure, and the separation between procedures is largest at intermediate signal strengths. U-eBH and J-eBH are the strongest competitors.

At independence (ρ=0\rho= 0) and μ=2.4\mu= 2.4, the power of D⋆D^\star is 29.41%, compared with 25.95% for U-eBH, 26.18% for J-eBH, and 14.55% for e-BH. The ordering is the same in the positive Toeplitz and negative equicorrelation panels of the figure.

Figure 2 reports the estimated difference in conditional expected power between D⋆D^\star and U-eBH over the full grid, in percentage points. The gain is positive at every setting. It is concentrated at intermediate signal strengths, roughly μ∈[2.2,2.8]\mu\in[2.2, 2.8], and decays toward both endpoints: at μ=1\mu= 1 the gain is 0.27 percentage points and at μ=4\mu= 4 it is 0.30 points, against a peak of 3.43 points. The peak is attained at (μ,ρ)=(2.4,0.1)(\mu,\rho) = (2.4, 0.1) in the positive family and at (μ,ρ)=(2.4,0.9)(\mu,\rho) = (2.4, 0.9) in the negative family.

Figure 2. Estimated power difference between D⋆D^\star and U-eBH, over the (μ,ρ)(\mu,\rho) grid.

Figure 3 reports the corresponding heatmaps for D⋆D^\star against the remaining e-value competitors. The maxima over the grid are 16.4 percentage points over e-BH, 15.7 over R1-eBH, 8.5 over R2-eBH, 8.0 over R-eBH, and 3.7 over J-eBH. The medians of these gains over the positive Toeplitz settings are 9.5, 9.2, 3.5, 3.4, and 1.6 percentage points for the same five competitors. Each median is at least 40% of the corresponding maximum, so the large gains are not confined to the settings where the maxima are achieved. Each heatmap shows the same pattern: a broad intermediate-signal region of improvement, with the gains decaying toward both endpoints. The intermediate-signal improvement persists in both covariance families and in both cases the heatmaps vary relatively little with ρ\rho.

Figure 3. Paired power differences of D⋆D^\star vs. each competitor, over the (μ,ρ)(\mu,\rho) grid. Color intensities are not comparable across panels.

Figure 4 reports the complete power and FDR curves for all seven e-value procedures at ρ∈{0,0.3,0.6,0.9}\rho\in\{0, 0.3, 0.6, 0.9\} in each dependence family. The power ordering established by

Power and FDR curves for all seven e-value procedures

Figure 4. Power and FDR curves for all seven e-value procedures at ρ∈{0,0.3,0.6,0.9}\rho\in\{0, 0.3, 0.6, 0.9\} in each dependence family. Ribbons are pointwise 95% Monte Carlo intervals; the dashed line in the FDR panels marks αK0/K=0.035\alpha K_0/K = 0.035.

Figure 1 persists across all eight panels. The FDR of every procedure lies below 0.035 throughout.

Discussion

This paper characterizes the simultaneous inclusion-probability optimization for e-BH under conditional certification and solves it. The certificate identity yields a coordinatewise upper bound, a single rule with one shared uniform variable attains every bound at once, and the equality conditions force any such rule to reject a prefix of the evidence ordering and fix its conditional rejection-set distribution. Simultaneous attainment implies optimality for every nonnegative weighted sum of inclusion probabilities, including expected true discoveries under any configuration of true and false nulls. The rule requires no additional tuning parameter beyond the target level, and its rejection set contains those of e-BH and U-eBH pathwise under the same uniform draw.

The optimization is relative to the certified class, which imposes budgets coordinate-by-coordinate, at each input on every coordinate, and membership is relative to the chosen evidence representation. Frameworks based on compound e-values [7] or e-closure (Xu et al., 2025) can permit procedures that need not satisfy these budgets, and the results do not constrain them. The result establishes optimality within the certified class, not admissibility among all FDR-controlling rules. The complete classes of Sun and Wang [11] address a separate question. The BY construction in the appendix optimizes over the calibrated evidence, so its optimality is relative to that representation rather than to all procedures using the original p-values.

Certification can be weakened to hold PP-almost surely. For each fixed distribution, budgets on the true nulls suffice for FDR control, and budgets on all coordinates preserve the inclusion bounds and power comparisons almost surely. The pointwise form is retained because it defines the optimization at every input without reference to a model.

Two directions remain. The certificate identity relies on a common certificate value on the rejection set, zero elsewhere, and a rejection count entering through its reciprocal. Whether other error criteria admit analogous identities and budgets is open. The false coverage rate is a candidate, but an optimality characterization for it would differ from the randomized improvement already developed for that criterion (Xu and Ramdas, 2025).

The results here optimize the decision given the evidence and an independent randomization seed. Optimizing evidence construction jointly with the decision under a specified model is a separate problem that this analysis does not address.

Appendix

This appendix collects the definitions of the randomized e-BH procedures of Xu and Ramdas (2025), together with the certificate bounds that place them in the class C\mathcal{C} of conditionally certified rules. The bounds below restate that guarantee in the certificate language of § 3, which the optimality analysis requires at every coordinate rather than only in aggregate over the nulls. In each case the bound can be derived from a randomized evidence vector whose coordinatewise conditional expectation is the original evidence, together with the self-consistency of e-BH applied to that vector, which is the step underlying the FDR proof of Wang and Ramdas [13]. Section A.1 and Section A.2 collect the definitions, Section A.3 proves the certificate bounds, and Section A.4 extends the construction to BY-calibrated p-values, establishing a pathwise nesting among the ordinary, shared-uniform, and optimal rejection sets.

Let G⊆[0,∞]\mathcal{G} \subseteq[0,\infty] be a closed set. For x∈[0,∞)x \in[0,\infty) let gL(x)=sup⁡{g∈G:g≤x}g_L(x) = \sup\{g \in\mathcal{G}: g \leq x\} and gU(x)=inf⁡{g∈G:g≥x}g_U(x) = \inf\{g \in\mathcal{G}: g \geq x\}, both of which lie in G\mathcal{G} when xx is within the range of G\mathcal{G}. Stochastic rounding of xx onto G\mathcal{G} is

TG(x,U)={x,x∈G, x<inf⁡G, x>sup⁡G, or gU(x)=∞,gU(x),gL(x)<x<gU(x)<∞ and U≤x−gL(x)gU(x)−gL(x),gL(x),gL(x)<x<gU(x)<∞ and U>x−gL(x)gU(x)−gL(x).T_{\mathcal{G}}(x,U) = \begin{cases} x, & x \in\mathcal{G},\ x < \inf\mathcal{G},\ x > \sup\mathcal{G},\ \text{or } g_U(x)=\infty,\\ g_U(x), & g_L(x) < x < g_U(x) < \infty\ \text{and}\ U \leq\dfrac{x-g_L(x)}{g_U(x)-g_L(x)},\\ g_L(x), & g_L(x) < x < g_U(x) < \infty\ \text{and}\ U > \dfrac{x-g_L(x)}{g_U(x)-g_L(x)}. \end{cases}

with U∼Uniform⁡(0,1)U \sim\operatorname{Uniform}(0,1). Elements of G\mathcal{G} and values outside the range of G\mathcal{G} are left unchanged. For xx strictly between adjacent grid points a<ba < b, the probability of rounding to bb is (x−a)/(b−a)(x-a)/(b-a), so that

EU[TG(x,U)]=gL(x)⋅gU(x)−xgU(x)−gL(x)+gU(x)⋅x−gL(x)gU(x)−gL(x)=x.\mathbb{E}_{U}[T_{\mathcal{G}}(x,U)] = g_L(x) \cdot\frac{g_U(x)-x}{g_U(x)-g_L(x)} + g_U(x) \cdot\frac{x-g_L(x)}{g_U(x)-g_L(x)} = x.

Applying TGT_{\mathcal{G}} to an e-value XX with UU independent of XX therefore produces an e-value TG(X,U)T_{\mathcal{G}}(X,U) with the same expectation.

The grid used by e-BH is K={0}∪{qr:r∈[K]}∪{∞}\mathcal{K} = \{0\} \cup\{q_r : r \in[K]\} \cup\{\infty\} where qr=K/(αr)q_r = K/(\alpha r) are the thresholds at which e-BH can reject. A coordinate already at a threshold is unchanged by rounding. The R1-eBH procedure applies e-BH to the rounded evidence on K\mathcal{K}, with independent uniform variables U1,U2,…,UKU_1, U_2, \ldots, U_K:

D1(x,U)=De(TK(x1,U1),TK(x2,U2),…,TK(xK,UK)).D_1(x,U) = D_e\left(T_{\mathcal{K}}(x_1,U_1), T_{\mathcal{K}}(x_2,U_2), \ldots, T_{\mathcal{K}}(x_K,U_K)\right).

The R2-eBH procedure replaces the fixed grid by a data-dependent threshold. Write re(x)=∣De(x)∣r_e(x) = |D_e(x)| and set

α^∗(x)=α(re(x)+1)/K,Gα={0,(α^∗(x))−1,∞}.\widehat{\alpha}^{*}(x) = \alpha(r_e(x)+1)/K,\quad\mathcal{G}_{\alpha} = \{0,(\widehat{\alpha}^{*}(x))^{-1},\infty\}.

The procedure applies stochastic rounding to each coordinate onto the grid Gα\mathcal{G}_{\alpha} and then applies e-BH to the rounded vector:

D2(x,U)=De(TGα(x1,U1),TGα(x2,U2),…,TGα(xK,UK)).D_2(x,U) = D_e\left(T_{\mathcal{G}_{\alpha}}(x_1,U_1), T_{\mathcal{G}_{\alpha}}(x_2,U_2), \ldots, T_{\mathcal{G}_{\alpha}}(x_K,U_K)\right).

The R-eBH procedure composes the two roundings. Let U′U' and U′′U'' be independent uniform vectors, set W=(TK(x1,U1′),TK(x2,U2′),…,TK(xK,UK′))W = (T_K(x_1,U'_1), T_K(x_2,U'_2), \ldots, T_K(x_K,U'_K)), and define

Dboth(x,(U′,U′′))=D2(W,U′′).D_{\mathrm{both}}(x,(U',U'')) = D_2(W,U'').

Shared and Coordinate-Specific Randomization

The U-eBH procedure applies e-BH to the scaled evidence xi/Ux_i/U with a single uniform variable U∼Uniform⁡(0,1)U \sim\operatorname{Uniform}(0,1) shared across all coordinates:

DU(x,U)=De(x1/U,x2/U,…,xK/U).D_U(x,U) = D_{\mathrm{e}}(x_1/U,x_2/U,\ldots,x_K/U).

Writing x[1]≥x[2]≥…≥x[K]x_{[1]} \ge x_{[2]} \ge\ldots\ge x_{[K]} for the decreasing order of xx, its rejection count is

rU(x,U)=max⁡({r∈[K]:U≤x[r]qr}∪{0}),r_U(x,U) = \max\left(\left\{r \in[K] : U \le\frac{x_{[r]}}{q_r}\right\} \cup\{0\}\right),

and DU(x,U)D_U(x,U) consists of the coordinates at ranks up to rU(x,U)r_U(x,U).

The J-eBH procedure uses independent uniform variables U1,U2,…,UKU_1,U_2,\ldots,U_K and applies the BH procedure at level α\alpha to the ratios Ui/xiU_i/x_i, with Ui/xi=∞U_i/x_i = \infty when xi=0x_i = 0. Its rejection count is

kJ(x,U)=max⁡({k∈[K]:∑i∈[K]1{Ui≤xiqk}≥k}∪{0}),k_J(x,U) = \max\left(\left\{k \in[K] : \sum_{i \in[K]} \mathbf{1}\left\{U_i \le\frac{x_i}{q_k}\right\} \ge k\right\} \cup\{0\}\right),

and DJ(x,U)={i∈[K]:Ui≤xiqkJ}D_J(x,U) = \left\{i \in[K] : U_i \le\frac{x_i}{q_{k_J}}\right\}, with DJ(x,U)=∅D_J(x,U) = \varnothing when kJ=0k_J = 0.

Conditional Certification of Randomized e-BH Procedures

Recall the certificate ZiZ_i of § 3.1. This subsection establishes the certificate bound for the three rounding procedures of Section A.1 and for the two uniform-based procedures of Section A.2.

Proposition A.1. The procedures R1-eBH, R2-eBH, and R-eBH satisfy EU[Zi(D(x,U))]≤xi\mathbb{E}_U[Z_i(D(x,U))] \le x_i for every x∈[0,∞)Kx \in[0,\infty)^K and every i∈[K]i \in[K].

Proof. Each of the three procedures has the form D(x,U)=De(W(x,U))D(x,U)=D_e(W(x,U)) for a jointly randomized nonnegative vector WW, and in each case the definition of stochastic rounding gives EU[Wi(x,U)]=xi\mathbb{E}_U[W_i(x,U)]=x_i. Since e-BH is self-consistent with respect to its input, De(W)D_e(W) is self-consistent with respect to WW: for every realization and every i∈De(W)i \in D_e(W) we have Wi≥K/(α∣De(W)∣)W_i \ge K/(\alpha|D_e(W)|). The certificate Zi(D)Z_i(D) is the coordinatewise smallest nonnegative vector supporting DD, so Zi(De(W))≤WiZ_i(D_e(W)) \le W_i pointwise. Taking expectations and applying EU[Wi]=xi\mathbb{E}_U[W_i]=x_i gives EU[Zi(D(x,U))]≤xi\mathbb{E}_U[Z_i(D(x,U))] \le x_i.

It remains to identify WW in the three cases. For R1-eBH,

W=(TK(x1,U1),TK(x2,U2),…,TK(xK,UK))W = (T_{\mathcal{K}}(x_1,U_1), T_{\mathcal{K}}(x_2,U_2), \ldots, T_{\mathcal{K}}(x_K,U_K))

with independent UiU_i, and EU[Wi]=xi\mathbb{E}_U[W_i]=x_i by the mean-preservation identity of stochastic rounding on K\mathcal{K}. For R2-eBH,

W=(TGα(x1,U1),TGα(x2,U2),…,TGα(xK,UK))W = (T_{\mathcal{G}_{\alpha}}(x_1,U_1), T_{\mathcal{G}_{\alpha}}(x_2,U_2), \ldots, T_{\mathcal{G}_{\alpha}}(x_K,U_K))

and the same identity on Gα\mathcal{G}_{\alpha} gives EU[Wi]=xi\mathbb{E}_{U}[W_i]=x_i. For R-eBH, let

W′=(TK(x1,U1′),TK(x2,U2′),…,TK(xK,UK′)),W'=(T_{\mathcal{K}}(x_1,U'_1),T_{\mathcal{K}}(x_2,U'_2),\ldots,T_{\mathcal{K}}(x_K,U'_K)),
W′′=(TGα(W′)(W1′,U1′′),TGα(W′)(W2′,U2′′),…,TGα(W′)(WK′,UK′′))W''=(T_{\mathcal{G}_{\alpha}(W')}(W'_1,U''_1),T_{\mathcal{G}_{\alpha}(W')}(W'_2,U''_2),\ldots,T_{\mathcal{G}_{\alpha}(W')}(W'_K,U''_K))

with U′′U'' independent of U′U'. Conditional on W′W', the mean-preservation identity on Gα(W′)\mathcal{G}_{\alpha}(W') gives EU′′[Wi′′∣W′]=Wi′\mathbb{E}_{U''}[W''_i\mid W']=W'_i, so E[Wi′′]=E[Wi′]=xi\mathbb{E}[W''_i]=\mathbb{E}[W'_i]=x_i.

Proposition A.2. The procedures U-eBH and J-eBH satisfy EU[Zi(D(x,U))]≤xi\mathbb{E}_{U}[Z_i(D(x,U))]\leq x_i for every x∈[0,∞)Kx\in[0,\infty)^K and every i∈[K]i\in[K].

Proof. For U-eBH, fix a rank r∈[K]r\in[K], write iri_r for the coordinate at rank rr so that xir=x[r]x_{i_r}=x_{[r]}, and write Z[r](A)=Zir(A)Z_{[r]}(A)=Z_{i_r}(A) for the certificate of that coordinate. Choose ℓ∈arg max⁡s≥rx[s]/qs\ell\in\operatorname*{arg\,max}_{s\geq r}x_{[s]}/q_s. Rank rr is rejected when some rank s≥rs\geq r is feasible, which is equivalent to

rU≥r⟺U≤x[ℓ]qℓ.r_U\geq r\Longleftrightarrow U\leq\frac{x_{[\ell]}}{q_{\ell}}.

On this event, rank ℓ\ell is feasible, so rU≥ℓr_U\geq\ell. Therefore

Z[r](DU)=Kα(rU∨1)1{rU≥r}≤Kαℓ1{U≤x[ℓ]qℓ}.Z_{[r]}(D_U)=\frac{K}{\alpha(r_U\vee1)}1\{r_U\geq r\}\leq\frac{K}{\alpha\ell}1\left\{U\leq\frac{x_{[\ell]}}{q_{\ell}}\right\}.

Taking expectations and using the uniformity of UU, we have

EU[Z[r](DU)]≤qℓmin⁡(1,x[ℓ]qℓ)=min⁡(qℓ,x[ℓ])≤x[ℓ]≤x[r].\mathbb{E}_{U}[Z_{[r]}(D_U)]\leq q_{\ell}\min\left(1,\frac{x_{[\ell]}}{q_{\ell}}\right)=\min(q_{\ell},x_{[\ell]})\leq x_{[\ell]}\leq x_{[r]}.

For J-eBH, write kJ=∣DJ∣k_J=|D_J|. The kJ=0k_J=0 case is trivial, so assume that kJ≥1k_J\geq1. For each coordinate i∈[K]i \in[K], define

Li(x,U−i)=max⁡({r∈[K]:1+∑j≠i1{Uj≤xj/qr}≥r}∪{0}).L_i(x,U_{-i}) = \max\left(\left\{r \in[K] : 1 + \sum_{j \ne i} \mathbf{1}\{U_j \le x_j/q_r\} \ge r\right\} \cup\{0\}\right).

This is the step-up count when coordinate ii is forced to be selected. By definition Li≥1L_i \ge1.

The sum runs over j≠ij \ne i, so LiL_i is a function of U−i=(U1,U2,…,Ui−1,Ui+1,…,UK)U_{-i} = (U_1,U_2,\ldots,U_{i-1},U_{i+1},\ldots,U_K) alone. Since kJk_J is the rejection count, at threshold qkJq_{k_J} the full sum satisfies ∑j∈[K]1{Uj≤xj/qkJ}≥kJ\sum_{j \in[K]} \mathbf{1}\{U_j \le x_j/q_{k_J}\} \ge k_J. This implies 1+∑j≠i1{Uj≤xj/qkJ}≥kJ1+\sum_{j \ne i}\mathbf{1}\{U_j \le x_j/q_{k_J}\} \ge k_J. Rank kJk_J is therefore feasible in the definition of LiL_i, and Li≥kJL_i \ge k_J.

We show that i∈DJi \in D_J if and only if Ui≤xi/qLiU_i \le x_i/q_{L_i}, and that kJ=Lik_J = L_i on {i∈DJ}\{i \in D_J\}.

If Ui≤xi/qLiU_i \le x_i/q_{L_i}, the definition of LiL_i gives 1+∑j≠i1{Uj≤xj/qLi}≥Li1+\sum_{j \ne i}\mathbf{1}\{U_j \le x_j/q_{L_i}\} \ge L_i. Since ii’s contribution equals one, the full sum satisfies ∑j∈[K]1{Uj≤xj/qLi}≥Li\sum_{j \in[K]}\mathbf{1}\{U_j \le x_j/q_{L_i}\} \ge L_i, so at least LiL_i coordinates satisfy their threshold at rank LiL_i and hence kJ≥Lik_J \ge L_i. Combined with kJ≤Lik_J \le L_i this gives kJ=Lik_J = L_i. The hypothesis is also the feasibility condition at rank kJk_J, since qLi=qkJq_{L_i} = q_{k_J}, so i∈DJi \in D_J. Conversely, if i∈DJi \in D_J, then Ui≤xi/qkJU_i \le x_i/q_{k_J}. Since kJ≤Lik_J \le L_i and qs=K/(αs)q_s = K/(\alpha s) is decreasing in ss, qkJ≥qLiq_{k_J} \ge q_{L_i}, so xi/qkJ≤xi/qLix_i/q_{k_J} \le x_i/q_{L_i} and hence Ui≤xi/qLiU_i \le x_i/q_{L_i}. Therefore i∈DJ⟺Ui≤xi/qLii \in D_J \Longleftrightarrow U_i \le x_i/q_{L_i}, and hence kJ=Lik_J = L_i whenever i∈DJi \in D_J.

On {i∈DJ}\{i \in D_J\} the certificate is K/(αkJ)K/(\alpha k_J) and zero elsewhere. Since kJ=Lik_J = L_i on that event and i∈DJ⟺Ui≤xi/qLii \in D_J \Longleftrightarrow U_i \le x_i/q_{L_i}, the certificate is qLiq_{L_i} on {Ui≤xi/qLi}\{U_i \le x_i/q_{L_i}\} and zero elsewhere, so

Zi(DJ)=qLi1{Ui≤xiqLi}.Z_i(D_J) = q_{L_i}\mathbf{1}\left\{U_i \le\frac{x_i}{q_{L_i}}\right\}.

The quantity LiL_i is a function of U−iU_{-i} at fixed xx, so

EUi[Zi(DJ)∣U−i]=qLiP(Ui≤xiqLi | U−i)=qLimin⁡(1,xiqLi)≤xi.\mathbb{E}_{U_i}[Z_i(D_J) \mid U_{-i}] = q_{L_i}\mathbb{P}\left(U_i \le\frac{x_i}{q_{L_i}} \,\middle|\, U_{-i}\right) = q_{L_i}\min\left(1,\frac{x_i}{q_{L_i}}\right) \le x_i.

Taking expectations over U−iU_{-i} gives EU[Zi(DJ)]≤xi\mathbb{E}_{U}[Z_i(D_J)] \leq x_i.

Certified BY-Calibrated Procedures

For r∈[K]r \in[K], write HK=∑r=1Kr−1H_K = \sum_{r=1}^{K} r^{-1} and tr=αr/(KHK)t_r = \alpha r/(K H_K), with t0=0t_0 = 0. The Benjamini-Yekutieli calibration function is

fBY(p)={K/(αr),tr−1<p≤tr,r∈[K],0,p>tK.f_{\mathrm{BY}}(p) = \begin{cases} K/(\alpha r), & t_{r-1} < p \leq t_r,\quad r \in[K],\\ 0, & p > t_K. \end{cases}

fBYf_{\mathrm{BY}} is nonnegative and nonincreasing, and

∫01fBY(p) dp=∑r=1KKαr⋅αKHK=1HK∑r=1K1r=1.\int_{0}^{1} f_{\mathrm{BY}}(p)\,dp = \sum_{r=1}^{K} \frac{K}{\alpha r} \cdot\frac{\alpha}{K H_K} = \frac{1}{H_K}\sum_{r=1}^{K}\frac{1}{r}=1.

If PiP_i is superuniform under HiH_i, then fBY(Pi)f_{\mathrm{BY}}(P_i) is an e-value for HiH_i with E[fBY(Pi)]≤1\mathbb{E}[f_{\mathrm{BY}}(P_i)] \leq1.

Because fBYf_{\mathrm{BY}} is nonincreasing, the e-BH thresholds on the calibrated evidence coincide with the BY thresholds on the original p-values.

For p-values P=(P1,P2,…,PK)P = (P_1, P_2, \ldots, P_K) and a uniform UU independent of PP, the BY procedure is DBY(P)=De(fBY(P))D_{\mathrm{BY}}(P) = D_e(f_{\mathrm{BY}}(P)), its shared-uniform version is U-BY(P,U)=DU(fBY(P),U)(P,U) = D_U(f_{\mathrm{BY}}(P),U), and the optimal certified rule applied to the same calibrated evidence is

DBY⋆(P,U)=D⋆(fBY(P),U)={i∈[K]:U≤αK∑j=1Kmin⁡{fBY(Pi),fBY(Pj)}}.D^\star_{\mathrm{BY}}(P,U) = D^\star(f_{\mathrm{BY}}(P),U) = \left\{i \in[K] : U \leq\frac{\alpha}{K}\sum_{j=1}^{K}\min\{f_{\mathrm{BY}}(P_i),f_{\mathrm{BY}}(P_j)\}\right\}.

Proposition A.3. Let P1,P2,…,PKP_1, P_2, \ldots, P_K be arbitrarily dependent, marginally superuniform p-values, and let U∼Uniform⁡(0,1)U \sim\operatorname{Uniform}(0,1) be independent of PP. Then DBY⋆D^\star_{\mathrm{BY}} controls the FDR

at αK0/K\alpha K_0/K, and

DBY(P)⊆U-BY(P,U)⊆DBY⋆(P,U)D_{\mathrm{BY}}(P) \subseteq\mathrm{U\text{-}BY}(P,U) \subseteq D^\star_{\mathrm{BY}}(P,U)

for every realization of UU.

Proof. Let Ei=fBY(Pi)E_i=f_{\mathrm{BY}}(P_i), so that DBY⋆(P,U)=D⋆(E,U)D^\star_{\mathrm{BY}}(P,U)=D^\star(E,U), DBY(P)=De(E)D_{\mathrm{BY}}(P)=D_e(E), and U-BY(P,U)=DU(E,U)\mathrm{U\text{-}BY}(P,U)=D_U(E,U) by the identifications above. Theorem 4.1 then gives EU[Zi(D⋆(E,U))]≤Ei\mathbb{E}_U[Z_i(D^\star(E,U))]\leq E_i for every ii, and Proposition 3.2 gives FDR control at αK0/K\alpha K_0/K. Since De(E)⊆DU(E,U)⊆D⋆(E,U)D_e(E)\subseteq D_U(E,U)\subseteq D^\star(E,U) by Proposition 4.1, the same containments hold for DBY(P)D_{\mathrm{BY}}(P), U-BY(P,U)\mathrm{U\text{-}BY}(P,U), and DBY⋆(P,U)D^\star_{\mathrm{BY}}(P,U).

The simulation setup of § 5.1 is used unchanged, with the BY-calibrated procedures added to the comparison and with the evidence supplied to the three procedures taken as fBY(Pi)f_{\mathrm{BY}}(P_i) for Pi=1−Φ(Zi)P_i=1-\Phi(Z_i), where Φ(⋅)\Phi(\cdot) denotes the Gaussian CDF.

Figure 5 reports the paired power differences for DBY⋆D^\star_{\mathrm{BY}} against BY and U-BY. The estimates reproduce the ordering DBY⊆U-BY⊆DBY⋆D_{\mathrm{BY}}\subseteq\mathrm{U\text{-}BY}\subseteq D^\star_{\mathrm{BY}} of Proposition A.3: DBY⋆D^\star_{\mathrm{BY}} has higher power than both, and the gain is larger against BY than against U-BY at every setting. The gain concentrates at intermediate signal strengths in both comparisons and decays toward the endpoints of μ\mu.

Figure 5. Paired power differences, in percentage points, over the (μ,ρ)(\mu,\rho) grid. Color intensities are not comparable across panels.

Figure 6 reports the power and FDR of the four procedures, with Benjamini-Hochberg (BH) procedure as a reference. The ordering DBY⊆U-BY⊆DBY⋆D_{\mathrm{BY}} \subseteq\mathrm{U\text{-}BY} \subseteq D_{\mathrm{BY}}^\star of Proposition A.3 appears as a power ordering in every panel, and the FDRs of the three procedures remain at or below αK0/K\alpha K_0/K throughout. BH has higher power but no FDR guarantee in the negative-equicorrelation family.

Figure 6. Power (top row) and FDR (bottom row) against μ\mu at independence (ρ=0\rho= 0), positive Toeplitz dependence (ρ=0.6\rho= 0.6), and negative equicorrelation (ρ=0.9\rho= 0.9), for the BY-calibrated procedures and the BH reference. Ribbons are pointwise 95% Monte Carlo intervals. The dashed line in the lower panels marks αK0/K=0.035\alpha K_0/K = 0.035.

References

  1. [1]Benjamini, Y. and 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.DOI
  2. [2]Benjamini, Y. and Yekutieli, D. (2001). The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4).DOI
  3. [3]Blanchard, G. and Roquain, E. (2008). Two simple sufficient conditions for FDR control. Electronic Journal of Statistics, 2(none).
  4. [4]Blier-Wong, C. and Wang, R. (2026). Improved thresholds for e-values. The Annals of Statistics, 54(4):1819–1842.
  5. [5]Croci, M., Fasi, M., Higham, N. J., Mary, T., and Mikaitis, M. (2022). Stochastic rounding: implementation, error analysis and applications. Royal Society Open Science, 9(3):211631.
  6. [6]Genovese, C. R., Roeder, K., and Wasserman, L. (2006). False discovery control with p-value weighting. Biometrika, 93(3):509–524.DOI
  7. [7]Ignatiadis, N., Wang, R., and Ramdas, A. (2024). E-values as unnormalized weights in multiple testing. Biometrika, 111(2):417–439.arxiv.org/abs/2204.12447
  8. [8]Lee, J. and Ren, Z. (2024). Boosting e-bh via conditional calibration.arxiv.org/abs/2404.17562
  9. [9]Ramdas, A. and Manole, T. (2026). Randomized and Exchangeable Improvements of Markov’s, Chebyshev’s and Chernoff’s Inequalities. Statistical Science, 41(1):121 – 142.arxiv.org/abs/2304.02611
  10. [11]Sun, L. and Wang, R. (2026). Admissibility and complete classes for false discovery rate control with e-values.arxiv.org/abs/2607.14380
  11. [12]Vovk, V. and Wang, R. (2021). E-values: Calibration, combination and applications. The Annals of Statistics, 49(3).DOI
  12. [13]Wang, R. and Ramdas, A. (2022). False Discovery Rate Control with E-values. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(3):822–852.arxiv.org/abs/2009.02824

Paper details

vlnc:W_y7jq7f3u
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents