On the expected runtime of multiple testing algorithms with bounded error
Georg Hahn

Julian Schwinger — Recollections from many decades
    Stanley Deser
    
==================================================




	Consider testing multiple hypotheses in the setting where the p-values of all hypotheses are unknown and thus have to be approximated using Monte Carlo simulations. One class of algorithms published in the literature for this scenario provides guarantees on the correctness of their testing result through the computation of confidence statements on all approximated p-values. This article focuses on the expected runtime of such algorithms and derives a variety of finite and infinite expected runtime results.


Keywords:
algorithm; bounded error; computational effort; finite expected runtime; multiple testing.





§ INTRODUCTION


Consider the testing of m ∈ hypotheses H_01,…,H_0m in a scenario in which the p-values p_1,…,p_m corresponding to the m hypotheses are unknown and thus have to be approximated using Monte Carlo simulations, for instance through bootstrap or permutation tests. Several algorithms published in the literature are designed for this scenario, either using a truncation rule to reach fast decisions <cit.> or using a heuristic approach to minimize the computational effort without truncation <cit.>.

In the aforementioned Monte Carlo scenario, the main focus of this article lies on the expected runtime of methods which aim to provide a guarantee of correctness on their decision (rejection or non-rejection) for each hypothesis through the computation of a sequence of confidence intervals on each p-value. For the special case of a single hypothesis, it is known that algorithms which compute (or rely on) the decision of one hypothesis with respect to a fixed threshold have an infinite expected runtime. This result is restated below in Section <ref>.

The novelty of this article consists in the generalisation of expected runtime results from single to multiple hypotheses. To be precise, under a simple and weak asymptotic condition on the length of the intervals produced by the confidence sequence, the article shows the following three main results. For applications relying on independent testing, meaning decisions of multiple hypotheses tested at a constant (Bonferroni-type) threshold, all but two hypotheses can be decided in finite expected runtime (Section <ref>). This result does not extend to applications which require full knowledge of all individual decisions, for instance step-up or step-down procedures, in which case no algorithm can guarantee even a single decision in finite expected runtime (Section <ref>). Simulations included in the conclusions (Section <ref>) show that in practice, however, the number of pending decisions is typically low.

Although unconsidered in their original publications, the expected runtimes derived in this article apply to a whole class of published algorithms in the literature. For instance, they apply to the algorithms of <cit.> which provide a guarantee on the correctness of the decision on each hypothesis through the computation of <cit.> confidence intervals. Expected runtimes also hold true for the confidence sequences of <cit.> employed in the methods of <cit.>, as they do for the confidence sequences of <cit.> and the binomial confidence intervals of <cit.> employed in <cit.>. The results of this article do not apply to the push-out design of <cit.> and the B-value design of <cit.>, which both achieve a bounded resampling risk without confidence statements on the p-values.



 §.§ A single decision requires infinite expected runtime


Following an argument similar to <cit.>, computing the decision of a hypothesis with random p-value requires an infinite expected runtime. Let m=1 hypothesis H_01 be given having a random p-value p_1. Assume a sequential algorithm A tests H_01 at some given threshold α by approximating p_1 through the drawing of Monte Carlo simulations and gives a guarantee of 1-ϵ on the correctness of its decision, where ϵ∈ (0,1).

Computing a decision on H_01 is equivalent to deciding whether p_1 ≤α or p_1 > α. For some p_0>α, consider testing H_0: p_1 ≤α against H_1: p_1=p_0. A test can be constructed by rejecting H_0 if and only if A does not reject H_01. Due to the guarantee of algorithm A, both the type 1 and type 2 errors of this test are ϵ. For such a sequential test, a lower bound on the runtime τ (the expected number of steps) is given by <cit.> as

    (τ|p=p_1) ≥ϵlog( ϵ/1-ϵ) + (1-ϵ) log( 1-ϵ/ϵ)/p_1 log( p_1/α) + (1-p_1) log( 1-p_1/1-α).

The same bound (<ref>) can be derived for the case p_0 ≤α. Abbreviate the numerator of (<ref>) by C and consider p_1 in a Bayesian setup such that the following condition is satisfied.

	
	Assume p_1 has a distribution function F(p_1) with derivative F'(α)>0, and that for a suitable γ>0, there exists a constant d>0 such that F'(p_1) ≥ d in (α,α+γ).

Amongst others, Condition <ref> is satisfied for the distributions of the exponential family. Under Condition <ref>, (τ) can be bounded by

    (τ)    = ∫_0^1 (τ|p=p_1) dF(p_1) ≥∫_α^α+γ(τ|p=p_1) dF(p_1)
       ≥ C · d ·∫_α^α+γ( p log( p/α) + (1-p) log( 1-p/1-α) )^-1 dp = ∞,

as the integrand is proportional to (p-α)^-2 as p →α. This proves an infinite expected runtime for the sequential test of H_0 and, equivalently, for algorithm A.





§ BONFERRONI-TYPE MULTIPLE TESTING IN EXPECTED FINITE TIME


Assume the testing of H_01,…,H_0m is carried out by comparing each p_i to a threshold value α_i ∈ (0,1), i ∈{ 1,…,m }, as done in, for instance, step-up and step-down procedures <cit.>. For this assume α_1 < ⋯ < α_m. In applications which rely on multiple testing at a constant (Bonferroni-type) threshold with a guarantee of correctness through confidence statements on the p-values, it will be shown that decisions on all but two hypotheses can be computed in expected finite time. The guarantee of correctness on all decisions is assumed to hold simultaneously for all hypotheses at 1-ϵ for some pre-specified ϵ∈ (0,1).

To be precise, a stronger statement is proven. For all but two hypotheses, it can be decided in expected finite time which of the intervals

    I = { [α_i,α_i+1): α_i<α_i+1, i=1,…,m-1}∪{ [0,α_1), [α_m,1] }

their p-values fall into.

As p-values are unknown, they are approximated through Monte Carlo simulations, and confidence statements are provided via confidence intervals. Let g(n) be the length of the confidence interval for a p-value after drawing n Monte Carlo simulations, and p̂_n be the maximum likelihood estimate of p based on n Monte Carlo simulations. Alternatively, any other estimate p̂_n is permissible whose deviation from the mean can be bounded with a Hoeffding type inequality <cit.> (see the proof of Theorem 1 in the Supplementary Material).

	
	Any confidence interval for p contains p̂_n. Moreover, g(n) ∈ o(n^γ) for some -1/2 < γ < -1/3.

Define D = min_I ∈ I d(p,∂ I) for a (random) p, where d(p,∂ I) is the distance of p to the boundary of I. If the distance of p to p̂_n is less than D/2 and the confidence interval for p has length g(n) ≤ D/2, the confidence interval for p will be entirely contained in some I ∈ I (assuming it contains p̂_n required by Condition <ref>). Therefore, a decision on which interval I ∈ I contains p is obtained on reaching the stopping time τ = inf{ n: |p̂_n-p|<D/2, g(n)<D/2 }.

Let τ_1,…,τ_m be the stopping times of the m p-values and τ_(1)≤⋯≤τ_(m) be their order statistic.


	
	Let the density of p be bounded above by some finite constant. Assume m ≥ 3. Under Condition <ref>, (τ_(m-s)) < ∞ for 2 ≤ s < m.


The proof of Theorem <ref> is found in the Supplementary Material. For the <cit.> correction, determining a I ∈ I containing the confidence interval of each hypothesis implies determining if the p-value of a hypothesis is above or below the constant testing threshold (subject to the overall 1-ϵ error probability), thus giving a decision on all but two hypotheses in finite expected time by Theorem <ref>. This result does not extend to multiple testing applications which depend on all individual decisions, for instance step-up or step-down procedures, in which case no algorithm can guarantee even a single decision in finite expected time (Section <ref>).

Section 1 of the Supplementary Material contains two results which highlight the asymptotic length of popular confidence intervals. These results are now used to establish that Condition <ref> is satisfied for a variety of confidence sequences and the algorithms they use:

	
  * The length of <cit.> confidence intervals is g(n) ∝ n^-1/2 (-logρ_n)^1/2 (see the proof in the Supplementary Material), where ρ_n is a sequence controlling how the overall risk ϵ is spent. If -log(ρ_n) ∝log(n) as in <cit.>, then g(n) ∈ o(n^γ) for any -1/2 < γ < -1/3. Since the <cit.> intervals contain p̂_n, Condition <ref> is satisfied. The intervals are employed in the algorithms of <cit.>.
	
  * Confidence intervals produced by the binomial confidence sequences of <cit.> satisfy g(n) ∝ n^-1/2{log(n log n) }^1/2 (see the proof in the Supplementary Material). In <cit.> it is shown that the intervals contain p̂_n, thus satisfying Condition <ref>. These confidence sequences are employed in the methods of <cit.>.
	
  * Intervals produced by the confidence sequences of <cit.> have length g(n) ∝ n^-1/2{log (log n) }^1/2 <cit.> and are centered around the empirical mean, thus satisfying Condition <ref>.
	
  * Binomial confidence intervals of <cit.> are employed in the methods of <cit.>. Being binomial exact intervals as the ones of <cit.>, they satisfy Condition <ref>.
	
  * Condition <ref> is satisfied for (asymptotic) maximum likelihood confidence intervals, given those are computed with a normal approximation. To be precise, the normal approximation produces confidence intervals of length g(n) ∝ n^-1/2, thus satisfying Condition <ref>.
	
  * Bootstrap confidence intervals for p can be written as [p̂+q_α,p̂+q_1-α] with α∈ (0,1), where q_α and q_1-α are the empirical α and 1-α quantiles of some bootstrap distribution F^∗ approximating an underlying distribution F that p is drawn from. Although specific to the application under consideration, the results of Theorem <ref> apply given it has been verified that q_1-α-q_α∈ o(n^γ) for some -1/2 < γ < -1/3. In particular, this is true if a normal approximation is used as in the case of maximum likelihood confidence intervals.






§ EXTENSION TO INFINITE EXPECTED RUNTIME FOR MULTIPLE TESTING


For multiple testing applications having the property that with non-zero probability, no decision on any hypothesis can be made until it is known whether a certain hypothesis is rejected or non-rejected (as it is the case, for instance, for step-up and step-down procedures), under reasonable assumptions on the distribution of p-values, an algorithm with both a guarantee of correctness and a finite expected runtime for any number of decisions cannot exist.

Consider testing the m hypotheses H_01,…,H_0m satisfying the following condition.

	
	The p-values p=(p_1,…,p_m) corresponding to H_01,…,H_0m have a joint distribution with support [0,1]^m and multivariate density f_p(p). For all δ>0 there exists a κ>0 such that f_p(p)>κ on [δ,1-δ]^m.

This condition is satisfied for many common densities. Assume testing is carried out with a step-up procedure that compares each p_i to a threshold value α_i, i ∈{1,…,m}, where α_1 < ⋯ < α_m (cf. Section <ref>). For any 0<η<(α_m-α_m-1)/4, define A = [ α_m-1 + 2η, α_m - 2η]^m-1× [α_m-η,α_m+η]. Let B=[δ_B,1-δ_B]^m and choose δ_B ∈ (0,1) in such a way that A ∩ B ≠∅.

Assuming the distribution of p=(p_1,…,p_m) satisfies Condition <ref> with δ=δ_B, draw a vector p̃=(p̃_1,…,p̃_m) from f_p conditional on being in A. By definition of A, p̃_m is the largest value in p̃ and will thus be compared to the threshold value α_m. By properties of a step-up procedure, as α_m-1 < p̃_i < p̃_m for all i ≠ m, no decision on any hypothesis can be made unless it is known whether p̃_m lies below or above α_m. In the former case, all hypotheses are rejected, in the latter case, all hypotheses are non-rejected. Under the additional assumption that the marginal distribution of p_m satisfies Condition <ref>, by Section <ref>, deciding H_0m requires an infinite expected time. Thus on the event {p ∈ A}, the expected time to decide any number of hypotheses is also infinite, (τ|p ∈ A) = ∞, where τ denotes the number of Monte Carlo simulations.

By the law of total expectation, the unconditional expected time can be bounded as (τ) ≥(τ|p ∈ A) ·(p ∈ A) = ∞, where it was used that (τ|p ∈ A) = ∞ and that f_p(p)>κ>0 on B implies (p ∈ A) ≥(p ∈ A ∩ B) > 0.

The above consideration proves an infinite expected runtime for step-up procedures for any desired number of decisions. It holds true, for instance, for the step-up procedures of <cit.>. A similar construction proves the same result for step-down procedures <cit.>. Extensions to other testing applications in which obtaining any decision can be made dependent on the decision of a single hypothesis are possible but application-specific.





§ CONCLUSIONS



According to Theorem <ref>, it can be decided in expected finite time for all but two hypotheses which interval I ∈ I in (<ref>) their p-values are contained in. For independent (Bonferroni-type) testing, this implies at most two pending decisions in finite expected time.

For step-up and step-down procedures, the situation is more involved. This is because the individual decision on a hypothesis need not matter in step-up (step-down) procedures so long as there exists another hypothesis with a larger (smaller) p-value for which a decision is available. As a consequence, having two undecided hypotheses in the sense of Theorem <ref> is not always representative of the actual number of decisions. Although in Section <ref>, this fact was used to show that under conditions, the expected time to compute any decision is infinite, in practice the decisions on a large number of hypotheses can often be computed quickly. For the <cit.> procedure with threshold α=0.1, Fig. <ref> displays the survival function of the number of undecided hypotheses which remain if, out of m ∈{ 10^1,10^2,10^3,10^4 } hypotheses, for only m-2 hypotheses it can be decided which I ∈ I in (<ref>) their p-values are contained in. The figure is based on R=1000 repetitions using p-values generated from the mixture distribution of <cit.>, consisting of a proportion π_0=0.8 drawn from a uniform distribution in [0,1] and the remaining proportion 1-π_0 drawn from a beta(0.5,25) distribution. As can be seen, often only a handful of hypotheses remain without decision. On this note, a related question addresses the optimal strategy (where optimality is defined with respect to the expected number of erroneously classified hypotheses) for allocating Monte Carlo simulations to multiple hypotheses in order to maximize the accuracy of the testing result. This has been addressed in the literature <cit.>.





§ APPENDIX

In the following, two versions of Hoeffding's inequality <cit.> are used in several places. Specifically, let X_1,…,X_n be independent random variables which are almost surely bounded, that is (X_i ∈ [a_i,b_i])=1 for some constants a_i, b_i and all i ∈{1,…,n}. Then by <cit.> the empirical mean X̅=(X_1+⋯+X_n)/n satisfies

    ( X̅-(X̅) ≤δ)    ≤exp( - 2 δ^2 n^2/∑_i=1^n (b_i-a_i)^2),
    ( | X̅-(X̅) | ≥δ)    ≤ 2 exp( - 2 δ^2 n^2/∑_i=1^n (b_i-a_i)^2).

In all following proofs, both inequalities will always be applied to a sum of independent Bernoulli random variables, in which case b_i=1 and a_i=0 for all i ∈{1,…,n}, and the denominator of the exponentials above can be simplified to ∑_i=1^n (b_i-a_i)^2=n.



 §.§ Auxiliary lemmas





The two-sided <cit.> confidence interval I_n with coverage probability 1-ρ_n based on n Monte Carlo simulations has length |I_n| ≤ 2 (2n)^-1/2 (-logρ_n)^1/2.


Suppose S<n exceedances are observed among n Monte Carlo simulations. Let ξ=(2n)^-1/2 (-logρ_n)^1/2 and regard the following probabilities conditional on S and n. The upper limit p_u of the interval I_n is the solution to (X ≤ S|p=p_u) = ρ_n, where  X ∼Binomial(n,p). If p > S/n +ξ, by Hoeffding's inequality,

    (X ≤ S)
    = ( X/n - ( X/n)
    ≤S/n - ( X/n) )
    ≤exp( - 2 (S/n-p)^2 n^2/n)
    < ρ_n,

where the first equality was obtained by dividing by n and subtracting (X/n)=p on both sides inside the probability, and where the Binomial variable X was expressed as X=X_1+⋯+X_n for some Bernoulli variables X_i, i ∈{1,…,n}. Thus p_u ≤ S/n + ξ. If S=n then p_u=1, implying p_u ≤ S/n + ξ. Similarly, the lower limit p_l of I_n satisfies p_l ≥ S/n - ξ. Together, |I_n| = p_u-p_l ≤ 2 ξ.


The proof of Lemma <ref> is analogous to the one of <cit.>.



The confidence interval I_n produced by the <cit.> and <cit.> Binomial confidence sequence based on n Monte Carlo simulations has length |I_n| ≤ n^-1/2{log(4n log n) }^1/2 for large enough n.


In <cit.> it is shown that (p ∉ I_n) ∝ (n log n)^-1/2. Since I_n need not be centered around the maximum likelihood estimate p̂_n, let I_n^s ⊇ I_n be the smallest symmetric interval around p̂_n containing I_n. Denote I_n^s = [p̂_n-t_n,p̂_n+t_n] for some t_n>0. Write p̂_n as the average of n independent Bernoulli(p) random variables. By Hoeffding's inequality, using (p̂_n)=p, one obtains (p ∉ I_n^s) = (|p̂_n-p|>t_n) ≤ 2 exp(-2 n t_n^2). Since (p ∉ I_n^s) ≤(p ∉ I_n), (p ∉ I_n^s) is at least of order (n log n)^-1/2. Thus, t_n ≤ (4n)^-1/2{log(4n log n) }^1/2 for large enough n.




 §.§ Proof of Theorem <ref>



The cdf of D = min_I ∈ I d(p,∂ I) is bounded above by

    (D ≤ t) = (∃ I ∈ I: d(p,∂ I) ≤ t) ≤∑_I ∈ I∫_0^t d(p,∂ I) f_p(p) dp ≤ (m+1) ∫_0^t U dp ≤ (m+1)U t,

where it was used that the cardinality of I is at most m+1, that the distance function d is bounded above by 1, and that the density f_p of the p-values is bounded above by a constant U.

In the following, an upper bound on the survival function (τ>t) will be derived. First, (|p̂_t-p| ≥ D/2) = (|p̂_t-(p̂_t)| ≥ D/2) ≤ 2 exp(-D^2 t/2) by Hoeffding's inequality, where it was used that the maximum likelihood estimate p̂_t can be expressed as an average of t Bernoulli(p) random variables. Second, using g(t) ∈ o(t^γ) by Condition <ref>, there exists a t_0>0 such that the event { g(t)<D/2 } is implied by { D>t^γ} for all t>t_0. Indeed, g(t) ∈ o(t^γ) and D t^-γ>1 imply the existence of a t_0>0 such that g(t) < g(t) D t^-γ < D/2 for all t>t_0.

The survival function (τ>t) can now be bounded above by conditioning on D. For t>t_0,

    (τ > t)    = (τ > t|D ≤ t^γ) (D ≤ t^γ)
    + (τ > t|D > t^γ) (D > t^γ)
       ≤ (m+1)U t^γ + (|p̂_t-p| ≥ D/2 ∨ g(t) ≥ D/2 |D > t^γ)
       ≤ (m+1)U t^γ + (|p̂_t-p| ≥ D/2 | D > t^γ)
       ≤ (m+1)U t^γ + 2 exp( -1/2 t^2γ+1),

where it was used that (τ > t|D ≤ t^γ) ≤ 1, (D > t^γ) ≤ 1 and that τ>t if either |p̂_t-p| ≥ D/2 or g(t) ≥ D/2 by the definition of τ in Section <ref>. The latter can be omitted as { D>t^γ} implies { g(t)<D/2 } for t>t_0. Using γ > -1/2 by Condition <ref>, t^2γ+1→∞ in the argument of the exponential function as t →∞ and thus (τ > t) ∈ O(t^γ).

Using the fact that the cumulative distribution function (cdf) of the rth order statistic X_(r) of n ∈ independent and identically distributed random variables X_1,…,X_n with cdf F_X can be expressed as F_X_(r)(x) = ∑_i=r^nni F_X^i(x) ( 1-F_X(x) )^n-i for r ∈{ 1,…,n } <cit.>, the expectation of τ_(m-s) can be bounded as

    (τ_(m-s))    = ∫_0^∞ 1-F_τ_(m-s)(t) dt
       = ∫_0^∞∑_i=0^m-s-1mi F_τ^i(t) ( 1-F_τ(t) )^m-i dt
    ≤∑_i=0^m-3mi∫_0^∞(τ>t)^m-i dt,

where it was used that the stopping times are non-negative, that F_τ(t) ≤ 1 and that 2 ≤ s < m implies m-s-1 ≤ m-3. Using (τ > t) ∈ O(t^γ), the integrals ∫_0^∞(τ>t)^m-i dt behave like ∫_0^∞ t^γ(m-i) dt and converge as γ < -1/3 (cf. Condition <ref>) and m ≥ 3 imply γ(m-i) < -1 for all i ∈{0,…,m-3 }.








[Andrews and Buchinsky, 2000]AndrewsBuchinsky2000
Andrews, D. and Buchinsky, M. (2000).
A Three‐step Method for Choosing the Number of Bootstrap
  Repetitions.
Econometrica, 68(1):23–51.

[Andrews and Buchinsky, 2003]AndrewsBuchinsky2003
Andrews, D. and Buchinsky, M. (2003).
Evaluation of a three-step method for choosing the number of
  bootstrap repetitions.
J Econometrics, 103(1-2):345–386.

[Armitage, 1958]Armitage1958
Armitage, P. (1958).
Numerical Studies in the Sequential Estimation of a Binomial
  Parameter.
Biometrika, 45(1-2):1–15.

[Benjamini and Hochberg, 1995]BenjaminiHochberg1995
Benjamini, Y. and Hochberg, Y. (1995).
Controlling the false discovery rate: A practical and powerful
  approach to multiple testing.
J Roy Stat Soc B Met, 57(1):289–300.

[Benjamini and Yekutieli, 2001]BenjaminiYekutieli2001
Benjamini, Y. and Yekutieli, D. (2001).
The control of the false discovery rate in multiple testing under
  dependency.
Ann Stat, 29(4):1165–1188.

[Besag and Clifford, 1991]BesagClifford1991
Besag, J. and Clifford, P. (1991).
Sequential Monte Carlo p-values.
Biometrika, 78(2):301–304.

[Bonferroni, 1936]Bonferroni1936
Bonferroni, C. (1936).
Teoria statistica delle classi e calcolo delle probabilità.
Pubblicazioni del R Istituto Superiore di Scienze Economiche e
  Commerciali di Firenze, 8:3–62.

[Clopper and Pearson, 1934]ClopperPearson1934
Clopper, C. and Pearson, E. (1934).
The Use of Confidence or Fiducial Limits Illustrated in the Case of
  the Binomial.
Biometrika, 26(4):404–413.

[Darling and Robbins, 1967a]DarlingRobbins1967b
Darling, D. and Robbins, H. (1967a).
Confidence sequences for mean, variance, and median.
P Natl Acad Sci USA, 58(1):66–68.

[Darling and Robbins, 1967b]DarlingRobbins1967a
Darling, D. and Robbins, H. (1967b).
Iterated logarithm inequalities.
P Natl Acad Sci USA, 57(5):1188–92.

[David and Nagaraja, 2003]DavidNagaraja2003
David, N. and Nagaraja, H. (2003).
Order Statistics.
Wiley.

[Davidson and MacKinnon, 2000]DavidsonMacKinnon2000
Davidson, R. and MacKinnon, J. (2000).
Bootstrap tests: How many bootstraps?
Economet Rev, 19(1):55–68.

[Ding et al., 2018]Ding2018
Ding, D., Gandy, A., and Hahn, G. (2018).
A simple method for implementing Monte Carlo tests.
arXiv:1611.01675, pages 1–17.

[Fay and Follmann, 2002]FayFollmann2002
Fay, M. and Follmann, D. (2002).
Designing Monte Carlo implementations of permutation or bootstrap
  hypothesis tests.
Am Stat, 56(1):63–70.

[Fay et al., 2007]Fay2007
Fay, M., Kim, H.-J., and Hachey, M. (2007).
On using truncated sequential probability ratio test boundaries for
  Monte Carlo implementation of hypothesis tests.
J Comput Graph Stat, 16(4):946–967.

[Gandy, 2009]Gandy2009
Gandy, A. (2009).
Sequential Implementation of Monte Carlo Tests With Uniformly
  Bounded Resampling Risk.
J Am Stat Assoc, 104(488):1504–1511.

[Gandy and Hahn, 2014]GandyHahn2014
Gandy, A. and Hahn, G. (2014).
MMCTest – A Safe Algorithm for Implementing Multiple Monte Carlo
  Tests.
Scand J Stat, 41(4):1083–1101.

[Gandy and Hahn, 2016]GandyHahn2016
Gandy, A. and Hahn, G. (2016).
A Framework for Monte Carlo based Multiple Testing.
Scand J Stat, 43(4):1046–1063.

[Gandy and Hahn, 2017]GandyHahn2017
Gandy, A. and Hahn, G. (2017).
QuickMMCTest: quick multiple Monte Carlo testing.
Stat Comput, 27(3):823–832.

[Guo and Peddada, 2008]GuoPedadda2008
Guo, W. and Peddada, S. (2008).
Adaptive Choice of the Number of Bootstrap Samples in Large Scale
  Multiple Testing.
Stat Appl Genet Mol Biol, 7(1):1–16.

[Hahn, 2019]HahnOptimal
Hahn, G. (2019).
Optimal allocation of Monte Carlo simulations to multiple hypothesis
  tests.
Stat Comput, pages 1–16.

[Hochberg, 1988]Hochberg1988
Hochberg, Y. (1988).
A sharper Bonferroni procedure for multiple tests of significance.
Biometrika, 75(4):800–802.

[Hoeffding, 1963]Hoeffding1963
Hoeffding, W. (1963).
Probability inequalities for sums of bounded random variables.
J Am Stat Assoc, 58(301):13–30.

[Holm, 1979]Holm1979
Holm, S. (1979).
A Simple Sequentially Rejective Multiple Test Procedure.
Scand J Stat, 6(2):65–70.

[Kim, 2010]Kim2010
Kim, H.-J. (2010).
Bounding the resampling risk for sequential Monte Carlo
  implementation of hypothesis tests.
J Stat Plan Infer, 140(7):1834–1843.

[Lai, 1976]Lai1976
Lai, T. (1976).
On Confidence Sequences.
Ann Stat, 4(2):265–280.

[Lin, 2005]Lin2005
Lin, D. (2005).
An efficient Monte Carlo approach to assessing statistical
  significance in genomic studies.
Bioinformatics, 21(6):781–787.

[Robbins, 1970]Robbins1970
Robbins, H. (1970).
Statistical methods related to the law of the iterated logarithm.
Ann Math Statist, 41(5):1397–1409.

[Rom, 1990]Rom1990
Rom, D. (1990).
A sequentially rejective test procedure based on a modified
  Bonferroni inequality.
Biometrika, 77(3):663–665.

[Sandve et al., 2011]Sandve2011
Sandve, G., Ferkingstad, E., and Nygård, S. (2011).
Sequential Monte Carlo multiple testing.
Bioinformatics, 27(23):3235–3241.

[Shaffer, 1986]Shaffer1986
Shaffer, J. (1986).
Modified Sequentially Rejective Multiple Test Procedures.
J Am Stat Assoc, 81(395):826–831.

[Sidak, 1967]Sidak1967
Sidak, Z. (1967).
Rectangular confidence regions for the means of multivariate normal
  distributions.
J Am Stat Assoc, 62(318):626–633.

[Silva and Assunção, 2013]SilvaAssuncao2013
Silva, I. and Assunção, R. (2013).
Optimal generalized truncated sequential Monte Carlo test.
J Multivariate Anal, 121:33–49.

[Silva and Assunção, 2018]SilvaAssuncao2018
Silva, I. and Assunção, R. (2018).
Truncated sequential Monte Carlo test with exact power.
Braz J Probab Stat, 32(2):215–238.

[Silva et al., 2009]Silva2009
Silva, I., Assunção, R., and Costa, M. (2009).
Power of the sequential Monte Carlo test.
Sequential Anal, 28(2):163–174.

[Simes, 1986]Simes1986
Simes, R. (1986).
An improved Bonferroni procedure for multiple tests of
  significance.
Biometrika, 73(3):751–754.

[van Wieringen et al., 2008]Wieringen2008
van Wieringen, W., van de Wiel, M., and van der Vaart, A. (2008).
A Test for Partial Differential Expression.
J Am Stat Assoc, 103(483):1039–1049.

[Wald, 1945]Wald1945
Wald, A. (1945).
Sequential Tests of Statistical Hypotheses.
Ann Math Statist, 16(2):117–186.


