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 , given e-values~, is , 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 hypotheses using e-values under arbitrary dependence, with target false discovery rate . 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 be a class of distributions on a common measurable space. For each , let denote the null hypothesis. For , let denote the set of true null hypotheses, with true nulls and alternatives. We write for the complement. We observe an evidence vector , finite almost surely. Each coordinate is an e-value for its hypothesis, i.e.,
The coordinates may be arbitrarily dependent, and no expectation restriction is imposed on when .
Let be an auxiliary random element with distribution on a measurable space , independent of under every . A randomized rejection rule is a measurable map . At evidence , the reported rejection set is . A deterministic rule is a special case in which does not depend on . We use and for probability and expectation over the randomization at fixed , and and when both the data and the randomization are integrated. The conditional inclusion probability of hypothesis under rule is
The rejection count is .
Error Control and Discovery Objectives
For a realized rejection set and a distribution , the false discovery proportion is
For a randomized rule , the false discovery rate is .
The rule is valid at level if for every . When , the average power of under is
We compare conditional inclusion probabilities at fixed inputs in the following sections. Averaging over then yields comparisons of average power.
The e-BH Rule and Self-Consistency
For a fixed , we write for its coordinates in decreasing order.
Define the e-BH thresholds and selected rank by
The e-BH rejection set is
By construction, . Under the e-value condition, the e-BH procedure controls the false discovery rate [13] with
Definition 2.1. A rejection set is self-consistent with respect to at level if
The empty set is self-consistent with respect to every .
For every , the e-BH rejection set is self-consistent with respect to , and every rejection set that is self-consistent with respect to is contained in . 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 , define its certificate by
The certificate equals when and zero otherwise. The self-consistency condition of Definition 2.1 is equivalent to the pointwise inequality for every . For , holds automatically.
For every , the false discovery proportion can be written in terms of the certificates of the true nulls. Substituting the definition of gives
Since only the certificates of the true nulls appear, we impose the conditional requirement on those coordinates.
Fix a set . A rule satisfies null-only conditional certification at if
where the expectation is over at fixed . We refer to the right-hand side as the certificate budget for coordinate . The certification condition (2) is stated in terms of the certificate . 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 supports a rule if is self-consistent with respect to for every fixed , i.e.,
Proposition 3.1. Fix a set . A rule satisfies (2) at if and only if there exists a nonnegative supporting vector such that
Proof. Suppose first that admits a supporting vector with the stated budgets. For every and every , self-consistency and nonnegativity give
as whenever , and whenever . Taking expectations and applying the budget on yields
Conversely, if (2) holds, take . The vector supports by construction, since on the rejection set, and the inequalities required by the proposition are exactly (2).
The certificate is the coordinatewise smallest nonnegative vector supporting a given rejection set. Imposing conditional budgets on is therefore equivalent to requiring the existence of supporting evidence satisfying those budgets.
Proposition 3.2. Fix . If a rule satisfies (2) at , then .
Proof. By the certificate representation of the false discovery proportion and iterated
expectation, we have
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 , a set , and a rule satisfying (2) at . We ask what these inequalities imply for the conditional inclusion probability . The calculation is pointwise in 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 and every coordinate , we have
To see this, if , then , so every term in the sum vanishes and both sides equal 0. If , then . The terms with equal , and the terms with vanish. Since there are terms of the first kind, the sum equals , and multiplying by gives 1. We now apply (3) to bound the conditional inclusion probability of a constrained coordinate.
Proposition 3.3. Let satisfy (2) at , and let . Then for every and every ,
Proof. Fix . Taking expectations in (3) with and writing gives
For , both certificates satisfy (2), and since the minimum is bounded above by either argument,
For , only the certificate of is constrained, so
There are coordinates with . Substituting these bounds gives
Combining with the elementary bound gives the stated inequality.
This is an oracle bound: it depends on the true configuration through and . The argument requires , since it uses the certificate budget for coordinate ; for , null-only certification gives no improvement over the elementary bound . Since 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 consists of all randomized rules satisfying
Every satisfies for every , by Proposition 3.2 applied with . By Proposition 3.1 applied with , a rule belongs to if and only if it admits a nonnegative supporting vector with
If satisfies the inequalities and , then , since e-BH is self-consistent with respect to its input. For an arbitrary supporting vector, self-consistency only implies .
The ordinary e-BH rule belongs to : its self-consistency gives the pointwise inequalities for every , 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 gives, for every , every , and every , , where
Optimality under Conditional Certification
Section 3.3 established that every satisfies the coordinatewise bound
for every and every . This section constructs a single rule in 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 be independent of , and define
With a single uniform variable independent of , write for the conditional inclusion probability. Because is uniform on , . Attaining these bounds does not by itself place in ; certification is verified in Theorem 4.1.
The score is monotone in . If , then for every , so . The rule therefore selects a prefix of the evidence ordering, and tied inputs are selected together. Zero inputs are never selected, as whenever . Because selects a prefix, it is convenient to describe it through the ordered coordinates.
For , define the ordered thresholds
and the rejection count
The coordinate at rank satisfies : the terms with contribute each, and the terms with contribute . The thresholds satisfy ; the nonnegativity is immediate from , and the monotonicity is verified as part of the proof of Theorem 4.1. The set therefore consists of the coordinates at ranks up to . We now show that is conditionally certified.
Proof. Both and the certificate are equivariant under relabeling of the coordinates, so it suffices to prove the claim for a sorted input and then extend by relabeling at the end. Fix in this ordering. Set , , and for . Using the definition of , we write
Thus, and . For define the intervals . The intervals are disjoint with union , since for every .
We claim that if and only if . Suppose first that , so that . Since , we have and therefore . To show that rank fails, note that . If , then , which contradicts ; hence , so and . Since rank fails the condition , we have , and combined with this gives .
Conversely, suppose with , so that and . From and we obtain , hence . For the upper endpoint, if , then , and if , then ; in either case . Together with this gives . The case occurs if and only if , which is equivalent to because and . Therefore
and
Returning to the fixed coordinate , we now compute its certificate expectation.
For , on the event , the coordinate at rank belongs to , so its certificate equals . Consequently,
Since and clipping at one cannot increase a gap, .
Substituting these bounds into the sum above gives
For an arbitrary input , let be the permutation that sorts in decreasing order, so . The score , the rule , and the certificate are equivariant under relabeling, so the inequality proved for the sorted input transfers to . Hence
for every . Therefore , 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 , every , and every ,
Proof. § 3.3 gives for every . Theorem 4.1 gives , and since by construction of , the claim follows.
Corollary 4.1 implies that every attains at most the marginal inclusion probabilities of 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 . 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 satisfy for every . If for some , then and for every .
Proof. By the certificate identity and the certificate budget,
Since the two ends are equal, every term in the sum is tight, and the claim follows. □
Lemma 2. Fix . Let satisfy and for every . Then is almost surely a prefix of the evidence ordering, i.e.,
Proof. A coordinate with satisfies and is selected almost surely. A coordinate with satisfies Lemma 1.
Fix and suppose . If , then is selected almost surely. For any with , monotonicity of gives , so is also selected almost surely.
If , Lemma 1 applied to gives and . For with , we have , so . Since pointwise, the difference is nonnegative with zero expectation, hence zero almost surely. Therefore almost surely. On the event , we have whenever , so and therefore . If , the case is vacuous.
Equal positive inputs satisfy . If this common value is at least 1, both are selected almost surely; otherwise, applying the argument above in both directions gives almost surely. Zero inputs have and are never selected. Therefore is almost surely a prefix of the evidence ordering.
Theorem 4.2. Fix and . For every random rejection set with for every ,
Moreover, if for every and equality holds, then has the same conditional distribution as at .
Proof. By the oracle bound of § 3.2 applied with ,
for every . Multiplying by and summing over gives the stated inequality.
For the uniqueness claim, suppose for every and equality holds in (5).
Every term is at most , which implies
for every . By Lemma 2, is almost surely a prefix of the evidence ordering.
Write for the coordinate at rank , so that , and set for , as in the proof of Theorem 4.1. For a prefix rule, if and only if the rejection count , so
is almost surely a prefix of the evidence ordering, i.e., is determined by . The tail probabilities determine the distribution of and therefore determine the distribution of . The rule is a prefix rule with the same tails, so and have the same distribution at input .
Corollary 4.2. For every , every weight vector with measurable for every , and every ,
Proof. Fix and . At each input , Theorem 4.2 applied with the weight vector gives
Taking expectations over we get:
Corollary 4.2 yields optimality for multiple objectives. With , it gives optimality for the expected number of rejections. With , it gives optimality for the expected number of true discoveries under any truth configuration; dividing by extends this to average power when .
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 , draw and sort in decreasing order. The sample is obtained by computing the thresholds and returning the prefix of length .
The U-eBH rule of Xu and Ramdas (2025) applies e-BH to the scaled inputs for a uniform independent of . Its rejection count is
and the rejection set consists of the coordinates at ranks up to . We use the same uniform seed for comparison.
Proposition 4.1. For every and every ,
Proof. Let denote the rejection rank of e-BH. If then the first inclusion above is trivial. Otherwise, by definition of , , so . Hence rank satisfies the U-eBH condition, which implies and therefore .
For the second inclusion, if rank satisfies , then
This implies and .
Since for every , the inclusion probability of at rank is at least that of , i.e.,
where .
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 hypotheses and target FDR . In each replication an alternative set is drawn uniformly among the subsets of size , independently of the noise, and the evidence is generated conditionally as
The hypotheses are against . True nulls have , at the boundary of the null hypothesis, and every alternative carries the same mean .
The covariance matrix takes one of two forms:
The parameter 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 takes equally spaced values on in increments of , and the dependence parameter takes equally spaced values on in increments of . Each setting is evaluated over Monte Carlo replications. The evidence supplied to the procedures is
The tuning parameter is held fixed across the signal-strength grid, so the evidence construction is identical at every .
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,
, 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 share a single uniform , which realizes the coupling of Proposition 4.1 for every and . 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 denote the evidence and the randomization in replication , let be the alternative set in that replication, and let . The realized false discovery proportion and true-discovery proportion of a rule are
The reported FDR and power are the averages and . Pointwise intervals use , where and are the sample mean and standard deviation of the corresponding replication-level quantity and is the Monte Carlo standard error. For against a competitor , the reported difference is the replication-level average of , with standard error computed from the . Differences and their intervals are reported in percentage points.
Simulation Results
Figure 1 reports power and FDR against at three representative dependence settings.
Figure 1. Power (top row) and FDR (bottom row) against at independence (), positive Toeplitz dependence (), and negative equicorrelation (). 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 .
Across the full grid, 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 over each competitor follows from the optimality theorem of § 4. The simulation quantifies the magnitude of the gaps, their concentration in the grid, and the ordering among the competitors.
Power increases with 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 () and , the power of 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 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 , and decays toward both endpoints: at the gain is 0.27 percentage points and at it is 0.30 points, against a peak of 3.43 points. The peak is attained at in the positive family and at in the negative family.
Figure 2. Estimated power difference between and U-eBH, over the grid.
Figure 3 reports the corresponding heatmaps for 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 .
Figure 3. Paired power differences of vs. each competitor, over the grid. Color intensities are not comparable across panels.
Figure 4 reports the complete power and FDR curves for all seven e-value procedures at in each dependence family. The power ordering established by

Figure 4. Power and FDR curves for all seven e-value procedures at in each dependence family. Ribbons are pointwise 95% Monte Carlo intervals; the dashed line in the FDR panels marks .
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 -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 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.
Stochastic Rounding and Related Procedures
Let be a closed set. For let and , both of which lie in when is within the range of . Stochastic rounding of onto is
with . Elements of and values outside the range of are left unchanged. For strictly between adjacent grid points , the probability of rounding to is , so that
Applying to an e-value with independent of therefore produces an e-value with the same expectation.
The grid used by e-BH is where 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 , with independent uniform variables :
The R2-eBH procedure replaces the fixed grid by a data-dependent threshold. Write and set
The procedure applies stochastic rounding to each coordinate onto the grid and then applies e-BH to the rounded vector:
The R-eBH procedure composes the two roundings. Let and be independent uniform vectors, set , and define
Shared and Coordinate-Specific Randomization
The U-eBH procedure applies e-BH to the scaled evidence with a single uniform variable shared across all coordinates:
Writing for the decreasing order of , its rejection count is
and consists of the coordinates at ranks up to .
The J-eBH procedure uses independent uniform variables and applies the BH procedure at level to the ratios , with when . Its rejection count is
and , with when .
Conditional Certification of Randomized e-BH Procedures
Recall the certificate 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 for every and every .
Proof. Each of the three procedures has the form for a jointly randomized nonnegative vector , and in each case the definition of stochastic rounding gives . Since e-BH is self-consistent with respect to its input, is self-consistent with respect to : for every realization and every we have . The certificate is the coordinatewise smallest nonnegative vector supporting , so pointwise. Taking expectations and applying gives .
It remains to identify in the three cases. For R1-eBH,
with independent , and by the mean-preservation identity of stochastic rounding on . For R2-eBH,
and the same identity on gives . For R-eBH, let
with independent of . Conditional on , the mean-preservation identity on gives , so .
Proposition A.2. The procedures U-eBH and J-eBH satisfy for every and every .
Proof. For U-eBH, fix a rank , write for the coordinate at rank so that , and write for the certificate of that coordinate. Choose . Rank is rejected when some rank is feasible, which is equivalent to
On this event, rank is feasible, so . Therefore
Taking expectations and using the uniformity of , we have
For J-eBH, write . The case is trivial, so assume that . For each coordinate , define
This is the step-up count when coordinate is forced to be selected. By definition .
The sum runs over , so is a function of alone. Since is the rejection count, at threshold the full sum satisfies . This implies . Rank is therefore feasible in the definition of , and .
We show that if and only if , and that on .
If , the definition of gives . Since ’s contribution equals one, the full sum satisfies , so at least coordinates satisfy their threshold at rank and hence . Combined with this gives . The hypothesis is also the feasibility condition at rank , since , so . Conversely, if , then . Since and is decreasing in , , so and hence . Therefore , and hence whenever .
On the certificate is and zero elsewhere. Since on that event and , the certificate is on and zero elsewhere, so
The quantity is a function of at fixed , so
Taking expectations over gives .
Certified BY-Calibrated Procedures
For , write and , with . The Benjamini-Yekutieli calibration function is
is nonnegative and nonincreasing, and
If is superuniform under , then is an e-value for with .
Because is nonincreasing, the e-BH thresholds on the calibrated evidence coincide with the BY thresholds on the original p-values.
For p-values and a uniform independent of , the BY procedure is , its shared-uniform version is U-BY, and the optimal certified rule applied to the same calibrated evidence is
Proposition A.3. Let be arbitrarily dependent, marginally superuniform p-values, and let be independent of . Then controls the FDR
at , and
for every realization of .
Proof. Let , so that , , and by the identifications above. Theorem 4.1 then gives for every , and Proposition 3.2 gives FDR control at . Since by Proposition 4.1, the same containments hold for , , and .
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 for , where denotes the Gaussian CDF.
Figure 5 reports the paired power differences for against BY and U-BY. The estimates reproduce the ordering of Proposition A.3: 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 .
Figure 5. Paired power differences, in percentage points, over the 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 of Proposition A.3 appears as a power ordering in every panel, and the FDRs of the three procedures remain at or below throughout. BH has higher power but no FDR guarantee in the negative-equicorrelation family.
Figure 6. Power (top row) and FDR (bottom row) against at independence (), positive Toeplitz dependence (), and negative equicorrelation (), for the BY-calibrated procedures and the BH reference. Ribbons are pointwise 95% Monte Carlo intervals. The dashed line in the lower panels marks .
References
- [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]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]Blanchard, G. and Roquain, E. (2008). Two simple sufficient conditions for FDR control. Electronic Journal of Statistics, 2(none).
- [4]Blier-Wong, C. and Wang, R. (2026). Improved thresholds for e-values. The Annals of Statistics, 54(4):1819–1842.
- [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]Genovese, C. R., Roeder, K., and Wasserman, L. (2006). False discovery control with p-value weighting. Biometrika, 93(3):509–524.DOI
- [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]Lee, J. and Ren, Z. (2024). Boosting e-bh via conditional calibration.arxiv.org/abs/2404.17562
- [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
- [11]Sun, L. and Wang, R. (2026). Admissibility and complete classes for false discovery rate control with e-values.arxiv.org/abs/2607.14380
- [12]Vovk, V. and Wang, R. (2021). E-values: Calibration, combination and applications. The Annals of Statistics, 49(3).DOI
- [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




