Multiple Hypothesis Tests Controlling Generalized Error
Rates for Sequential Data
Jay Bartroff∗

arXiv:1406.5933v4 [stat.ME] 19 Dec 2016

Department of Mathematics, University of Southern California, Los Angeles, California, USA

Abstract
The γ-FDP and k-FWER multiple testing error metrics, which are tail probabilities of
the respective error statistics, have become popular recently as alternatives to the FDR and
FWER. We propose general and flexible stepup and stepdown procedures for testing multiple
hypotheses about sequential (or streaming) data that simultaneously control both the type I
and II versions of γ-FDP, or k-FWER. The error control holds regardless of the dependence
between data streams, which may be of arbitrary size and shape. All that is needed is a test
statistic for each data stream that controls the conventional type I and II error probabilities,
and no information or assumptions are required about the joint distribution of the statistics
or data streams. The procedures can be used with sequential, group sequential, truncated,
or other sampling schemes. We give recommendations for the procedures’ implementation
including closed-form expressions for the needed critical values in some commonly-encountered
testing situations. The proposed sequential procedures are compared with each other and
with comparable fixed sample size procedures in the context of strongly positively correlated
Gaussian data streams. For this setting we conclude that both the stepup and stepdown
sequential procedures provide substantial savings over the fixed sample procedures in terms of
expected sample size, and the stepup procedure performs slightly but consistently better than
the stepdown for γ-FDP control, with the relationship reversed for k-FWER control.

1

Introduction and Summary

Driven in part by modern applications involving high-dimensional models or the need for
many comparisons in areas such as high-throughput gene and protein expression data, brain
imaging, and astrophysics, there has been much interest and innovation during recent decades
in statistical methodology involving multiple testing error rates which are less stringent than
the classical familywise error rate (FWER), the probability of rejecting at least one true
null hypothesis. Hommel and Hoffmann (1988) proposed the k-FWER, the probability of
rejecting at least k ≥ 1 true null hypotheses, and this was independently proposed later by
Lehmann and Romano (2005). Benjamini and Hochberg (1995) proposed the false discovery
rate (FDR), the expectation of the false discovery proportion (FDP), the latter being the
0

Key words and phrases: false discovery proportion, familywise error, generalized error rate, high-dimensional
statistics, multiple comparisons, multiple testing, sequential analysis, sequential hypothesis testing, stepdown procedure, stepup procedure, Wald approximations.
∗
email: bartroff@usc.edu. This work was partially supported by National Science Foundation grant DMS-1310127
and National Institutes of Health grant R01 GM068968.

1

proportion of rejected null hypotheses that are true. As a generalization of the FDR, Lehmann
and Romano (2005) proposed using the probability that the FDP exceeds a fixed value γ ∈
[0, 1), which has come to be known as the γ-FDP. Recently, Guo, He, and Sarkar (2014)
proposed a further generalization of the γ-FDP. Each of these authors also supplied procedures
to control the respective generalized error rates under various dependence assumptions on the
data, ranging from independence to positive regression dependency on subsets (Benjamini and
Yekutieli, 2001) to no assumptions at all. Many other authors have also provided innovative
new procedures and theory surrounding these generalized error rates and we do not attempt
to summarize this large and growing literature here, but instead refer the reader to Guo et al.
(2014) and the references therein.
All of the references mentioned above take as their starting point a set of valid p-values
corresponding to fixed sample size tests for the list of null hypotheses of interest. However, in
some areas of application the data in a multiple testing setup does not naturally occur in a fixed
sample but rather arrives sequentially (or in groups) in time, referred to as “streaming” data in
some applications. An obvious example is in biomedical clinical trials with multiple endpoints
or arms (e.g., Jennison and Turnbull, 2000, Chapter 15), but others areas with naturally
sequential data abound including certain high-throughput sequencing technologies (Salzman
et al., 2011; Jiang and Salzman, 2012), multi-channel changepoint detection (Tartakovsky et al.,
2003), biosurveillance (Mei, 2010), acceptance sampling with multiple criteria (Baillie, 1987),
financial data (Lai and Xing, 2008), and some agricultural studies (Clements et al., 2014). Only
recently have general and flexible multiple testing procedures suited for the particular needs
of sequential data been proposed in literature. Bartroff and Lai (2010) proposed a sequential
version of Holm’s (1979) FWER-controlling procedure. De and Baron (2012a,b) proposed
procedures controlling both the type I and II FWER under the restriction that all data streams
be sampled until accept/reject decisions can be reached for all null hypotheses simultaneously,
and Bartroff and Song (2014b) proposed a procedure lifting this restriction. Like Holm’s
procedure, each of these sequential procedures mentioned so far has guaranteed FWER control
under arbitrary dependence of data streams. Bartroff and Song (2014a) proposed an analogous
procedure controlling FDR and its type II analog, the false nondiscovery rate, on sequential
data.
The purpose of this paper is to provide general and flexible procedures for controlling kFWER and γ-FDP on sequential data. By “general and flexible” we mean procedures that
can test J ≥ 2 arbitrary null hypotheses H (1) , . . . , H (J) about J data streams
(1)

(1)

(2)

(2)

(J)

(J)

Data stream 1: X1 , X2 , . . .
Data stream 2: X1 , X2 , . . .
..
.
Data stream J:

(1)

X1 , X2 , . . . ,
(j)

respectively, of arbitrary size, shape, and dependence. In particular, each data point Xn
may itself be the vector of observations from the nth group, corresponding to group sequential
sampling. This setup is formalized below. In particular we define stepdown and stepup pro(j)
(j)
cedures that require only arbitrary sequential test statistics Λ(j) (n) = Λ(j) (n)(X1 , . . . , Xn )
for each stream j = 1, . . . , J that control the conventional type I and II error probabilities for
each individual null hypothesis H (j) , and combine them to give a sequential multiple testing
procedure, i.e., a collection of J sequential stopping and decision rules for each data stream,
that controls k-FWER or γ-FDP at a prescribed level under arbitrary dependence structure
between data streams. In this regard our procedures can be viewed as extensions to the se-

2

quential realm of the procedures of Lehmann and Romano (2005) and Romano and Shaikh
(2006a,b) who accomplished this in the fixed sample setup. Indeed, our approach owes much
to the work of these authors and, in particular, we utilize the same stepup and stepdown
values as those papers. Sarkar (2007, 2008) and Guo et al. (2014) have furthered the work of
these authors by developing stepup and stepdown fixed sample size procedures which utilize
the joint null distribution of the p-values and, in some cases, dominate previously proposed
procedures while controlling generalized error rates. While we expect that these innovations
by Sarkar and his coauthors can similarly be extended to the sequential domain, since our goal
here is to propose procedures that don’t require knowledge (or modeling) of joint distributions,
we have not pursued those extensions here.
An additional aspect of our approach is that our procedures may be able to simultaneously
control both the type I and II versions of the generalized error metrics at prescribed values,
which is a possibility opened up by the sequential setting considered. As with single hypothesis
testing, if the prescribed type II error rate (or equivalently, power) is not well-motivated, then
its strict control can be dispensed with or used as a surrogate for other operating characteristics
of interest, such as average sample size. For this reason and others discussed in Section 4, there
we provide versions of the procedures that control the type I generalized error rate but not
necessarily the type II version, and these procedures can be used with arbitrary acceptance
rules for the null hypotheses.
Regarding our sequential setup, we remark that in order to sequentially test J ≥ 2 null
hypotheses, one could simply apply J chosen sequential stopping rules to the data streams,
calculate the (appropriately adjusted) p-values upon stopping, and then apply a fixed-sample
procedure to the p-values. However, this “naive” method will in general be inefficient compared
to the procedures proposed herein since the stopping rules do not explicitly take the multiple
testing error metric into account. Moreover, the naive method will not in general control
both the type I and II multiple testing error rates which, even when this feature is not a
priority of the statistician as mentioned in the previous paragraph, means that the relationship
between the naive method’s stopping rule and its power is not well understood, unlike the
proposed procedures. Nonetheless, our approach below could be applied by taking the test
statistics Λ(j) (n) to be sequential p-values, making it look more like the fixed sample size
procedures. Instead we have chosen to use arbitrary sequential test statistics to maintain
generality and to make the resulting procedure more user-friendly, given that other types of
test statistics like log-likelihood ratios (or simple functions thereof) are much more commonly
used with sequential data than sequential p-values. This is perhaps due to the complexity and
non-uniqueness of sequential p-values in all but the simplest cases; see Jennison and Turnbull
(2000, Chapters 8.4 and 9).
The remainder of this paper is organized as follows. After introducing the notation and
setup in Section 2, in Section 3.1 we define a “generic” sequential stepdown procedure that
accepts arbitrary stepdown values (5), special cases of which are given in Sections 3.1.2 and
3.1.3 which control type I and II γ-FDR and k-FWER, respectively. An analogous development
of stepup procedures in given in Section 3.2. Section 4 gives versions of these procedures
with only explicit rejection rules for use when the type II error rate is not well motivated
or there is a restriction on maximum sample size. In Section 5 we give recommendations
for implementing the procedures by reviewing how to implement sequential single-hypothesis
tests in some commonly-encountered situations, and we give closed-form expressions for the
needed critical values in Theorem 5.1. Section 5.2 discusses how to implement group sequential
sampling. Section 6 contains the results of a numerical study comparing the proposed stepup,
stepdown, and comparable fixed sample size procedures in a setting of strongly positively
correlated Gaussian data streams. In Section 7 we summarize our recommendations. All

3

proofs are delayed until Section 8.

2
2.1

Setup
Data Streams, Hypotheses, and Error Metrics

Assume that there are J ≥ 2 data streams (1). In general we make no assumptions about the
(j)
dimension of the sequentially-observed data Xn , which may themselves be vectors of varying
(j)
(j)
size, nor about the dependence structure of within-stream data Xn , Xm or between-stream
0
(j)
(j )
data Xn , Xm (j 6= j 0 ). In particular there can be arbitrary “overlap” between data streams,
an extreme case being that all the data streams are the same, which is equivalent to testing
multiple hypotheses about a single data source. For any positive integer j let [j] = {1, . . . , j}.
For each data stream, indexed by j ∈ [J], assume that there is a parameter vector θ(j) ∈ Θ(j)
(j)
(j)
determining that distribution of the stream X1 , X2 , . . ., and it is desired to test a null
hypothesis H (j) versus the alternative hypothesis G(j) , where H (j) and G(j) are disjoint subsets
of the parameter space Θ(j) containing θ(j) . The null H (j) is considered true if θ(j) ∈ H (j) ,
and false if θ(j) ∈ G(j) . The global parameter θ = (θ(1) , . . . , θ(J) ) is the concatenation of the
individual parameters and is contained in the global parameter space Θ = Θ(1) × · · · × Θ(J) .
Let
T (θ) = {j ∈ [J] : θ(j) ∈ H (j) }
(2)
denote the indices of the true null hypotheses when θ is the true global parameter, and
F(θ) = {j ∈ [J] : θ(j) ∈ G(j) }

(3)

the indices of the false null hypotheses.
It may appear that the notation (1) for the data streams restricts us to fully-sequential
sampling where the streamwise sample sizes may take any value 1, 2, . . . ad infinitum. However,
(j)
since the observations Xn themselves may be of arbitrary size and shape, group sequential
(and even variable-stage size) sampling fits into this framework. To wit, the nth “observa(j)
(j)
(j)
(j)
tion” Xn in the jth stream may actually be the nth group Xn = (Xn,1 , . . . , Xn,` ) of size `.
Moreover, the group size ` may vary with n and may even be data-dependent, e.g., determined
by some type of adaptive sampling. Similarly, truncated sampling can be implemented for the
(j)
(j)
jth stream by defining Xn = ∅ for all n > N
for some stream-specific truncation point
(j)
N , or globally for all streams by replacing statements like “for some n” in what follows with
“for some n ≤ N ,” for some global truncation point N .
The FDP is formally defined as

 the number of H (j) rejected, j ∈ T (θ) , if the denominator is positive,
FDP(θ) =
(4)
the number of H (j) rejected

0,
otherwise.
For example, as mentioned above, Benjamini and Hochberg’s (1995) FDR is the expectation
Eθ (FDP(θ)) of the FDP. Since we will consider procedures that simultaneously control both
the type I and type II versions of the generalized error rates, we also define the type II analog
of FDP, which we call the false nondiscovery proportion (FNP),

 the number of H (j) accepted, j ∈ F(θ) , if the denominator is positive,
FNP(θ) =
the number of H (j) accepted

0,
otherwise.

4

With FDP and FNP nailed down, for γ1 , γ2 ∈ [0, 1) we define
γ1 -FDP(θ) = Pθ (FDP(θ) > γ1 )

and γ2 -FNP(θ) = Pθ (FNP(θ) > γ2 ).

Similarly, for k-FWER we will distinguish the type I and II versions by, for k1 , k2 ∈ [J],
defining
k1 -FWER1 (θ) = Pθ (at least k1 null hypotheses H (j) rejected, j ∈ T (θ)),
k2 -FWER2 (θ) = Pθ (at least k2 null hypotheses H (j) accepted, j ∈ F(θ)).
We will omit the argument θ from these quantities in what follows when it causes no confusion.

2.2

Test Statistics and Critical Values

The building blocks of the sequential procedures defined below are J individual sequential test
statistics {Λ(j) (n)}j∈[J], n≥1 , where Λ(j) (n) is the statistic for testing H (j) vs. G(j) based on
(j)

(j)

(j)

the data X1 , X2 , . . . , Xn available from the jth stream at time n. For example, Λ(j) (n)
may be a sequential log likelihood ratio statistic for testing H (j) vs. G(j) . The stepup and
stepdown procedures proposed below will be defined in terms of given constants
0 ≤ α1 ≤ . . . ≤ αJ ≤ 1

and

0 ≤ β1 ≤ . . . ≤ βJ ≤ 1,

(5)

which we will refer to as step values, the αj corresponding to type I error control and the βj
to type II. These values will be used in a similar way as in fixed sample size stepdown and
stepup procedures, which we review now for comparison with what follows. Based on p-values
p(j1 ) ≤ . . . ≤ p(jJ ) with p(j) corresponding to H (j) , the stepdown procedure based on constants
αj satisfying (5) rejects H (j1 ) , . . . , H (jd ) where d = max{i ∈ [J] : p(ji0 ) ≤ αi0 for all i0 ≤
i} (accepting all nulls if the maximum doesn’t exist), whereas the stepup procedure rejects
H (j1 ) , . . . , H (ju ) where u = max{i ∈ [J] : p(ji ) ≤ αi } (accepting all nulls if the maximum
doesn’t exist). Note that d ≤ u so that the stepup procedure rejects at least as many null
hypotheses as the corresponding stepdown procedure using the same step values.
Given step values {αj , βj }j∈[J] , for each test statistic Λ(j) (n) we assume the existence of
(j)

(j)

critical values {Aw , Bw }w∈[J] such that
(j)

for all

θ(j) ∈ H (j)

(6)

(j)

for all

θ(j) ∈ G(j)

(7)

(j)
Pθ(j) (Λ(j) (n) ≥ Bw
some n, Λ(j) (n0 ) > A1 all n0 < n) ≤ αw
(j) 0
0
Pθ(j) (Λ(j) (n) ≤ A(j)
w some n, Λ (n ) < B1 all n < n) ≤ βw
(j)

(j)

for all w ∈ [J]. The critical values A1 , B1 are simply the critical values for the sequential
(j)
(j)
test that samples until Λ(j) (n) 6∈ (A1 , B1 ), and this test has type I and II error probabilities
(j)
bounded above by α1 and β1 , respectively. The values Bw , w ∈ [J], are then such that the
(j)
(j)
similar sequential test with critical values A1 and Bw has type I error probability αw , which
(j)
is just a restatement of (6), with an analogous statement holding for critical values Aw and
(j)
(j)
(j)
B1 , type II error probability βw , and (7). The reason that critical values A1 and Bw are
(j)
(j)
considered in (6) for type I error probability control and not, say, Aw and Bw is that the
(j)
(j)
procedures defined below will sample during the ith stage using critical values Aw and Bw0
for some fixed values w, w0 ∈ [J] determined by the data in the previous stages 1, . . . , i − 1.
(j)
(j)
The probability that, during the ith stage, Λ(j) (n) ≥ Bw0 before Λ(j) (n) ≤ Aw will then be
(j)
(j)
bounded above by the corresponding statement with Aw replaced by A1 , using the fact that

5

(j)

(j)

A1 ≤ Aw by (8), and thus this probability related to (6) after bounding w0 . Analogous
statements apply regarding bounding the type II error probability.
In all commonly-encountered testing situations there are standard sequential statistics
whose critical values can be chosen that satisfy these error bounds, for any given {αj , βj }j∈[J]
(Bartroff and Song, 2014b, give examples). Without loss of generality we assume that, for
each j ∈ [J],
(j)

(j)

(j)

(j)

(j)

(j)

A1 ≤ A2 ≤ . . . ≤ AJ ≤ BJ ≤ BJ−1 ≤ . . . ≤ B1 ,

(8)

(j)

(j)

(9)

(j)

(j)

(10)

Aw = Aw+1 if and only if βw = βw+1 ,
Bw = Bw+1 if and only if αw = αw+1 .

A simplistic example of how critical values (8) are used in our sequential multiple testing
procedure will be given in the last two paragraphs of Section 3.1.1.
The sequential multiple testing procedures proposed below will involve ranking the test
statistics associated with different data streams, which may be on completely different scales
in general, so for each stream j we introduce a standardizing function ϕ(j) (·) which will be
applied to the statistic Λ(j) (n) before ranking. The standardizing functions ϕ(j) can be any
(j)
(j)
increasing functions such that ϕ(j) (Aw ) and ϕ(j) (Bw ) do not depend on j, and we let
aw = ϕ(j) (A(j)
w )

(j)
and bw = ϕ(j) (Bw
),
(j)

j, w ∈ [J],

(11)

(j)

denote these common values. Given critical values {Aw , Bw }j,w∈[J] satisfying (6)-(7), one
may choose arbitrary values {aw , bw }w∈[J] satisfying the same monotonicity conditions as the
(j)

(j)

{Aw , Bw } according to (9)-(10) and then define the standardizing functions ϕ(j) (·) to be
increasing, piecewise linear functions satisfying (11). For example, if all the αw are distinct
and the βw are distinct then a simple choice for the {aj , bj } are the integers
a1 = −J,

a2 = −J + 1,

...,

aJ = −1,

bJ = 1,

bJ−1 = 2,

...,

b1 = J.

In any case, the assumptions on the critical values and standardizing functions imply that the
e (j) (n) = ϕ(j) (Λ(j) (n))
aw must be nondecreasing and the bw nonincreasing. Finally, we denote Λ
and then (6)-(7) can be written
e (j) (n) ≥ bw some n, Λ
e (j) (n0 ) > a1 all n0 < n) ≤ αw for all θ(j) ∈ H (j)
Pθ(j) (Λ
e (j) (n) ≤ aw some n, Λ
e (j) (n0 ) < b1 all n0 < n) ≤ βw for all θ(j) ∈ G(j) ,
Pθ(j) (Λ

(12)
(13)

for all j, w ∈ [J].

3 Procedures Controlling Type I and II Generalized
Error Rates
3.1
3.1.1

Stepdown Procedures
The Generic Sequential Stepdown Procedure

Here we define a generic sequential stepdown procedure, special cases of which will be used
to define the type I and II k-FWER and γ-FDP controlling sequential procedures below. We
assume that step values {αj , βj }j∈[J] satisfying (5) are given and that the test statistics and
critical values satisfy the assumptions in Section 2.2 with respect to these values.

6

We will describe the procedure in terms of stages of sampling, between which reject/accept
decisions are made. Let Ji ⊆ [J] (i = 1, 2, . . .) denote the index set of the active data streams
(i.e., those whose corresponding null hypothesis H (j) has been neither accepted nor rejected
yet) at the beginning of the ith stage of sampling, and ni will denote the cumulative sample
size of any active test statistic up to and including the ith stage. The total number of null
hypotheses that have been rejected (resp. accepted) at the beginning of the ith stage will be
denoted by ri (resp. ci ). Accordingly, set J1 = [J], n0 = 0, r1 = c1 = 0. Let | · | denote
set cardinality. Then the ith stage of sampling (i = 1, 2, . . .) of the Generic Sequential
Stepdown Procedure with step values {αj , βj }j∈[J] proceeds as follows.
(j)

1. Sample the active streams {Xn }j∈Ji , n>ni−1 until n equals
n
e (j) (n) 6∈ (ac +1 , br +1 ) for some
ni = inf n > ni−1 : Λ
i
i

o
j ∈ Ji .

(14)

2. Order the active test statistics
e (j(ni ,1)) (ni ) ≤ Λ
e (j(ni ,2)) (ni ) ≤ . . . ≤ Λ
e (j(ni ,|Ji |)) (ni ),
Λ
where j(ni , `) denotes the index of the `th ordered active statistic at the end of stage i.
e (j) (ni ) ≥ br +1 for some
3. (a) If the upper boundary in (14) has been crossed, that is, if Λ
i
j ∈ Ji , then reject the mi ≥ 1 null hypotheses
H (j(ni ,|Ji |)) , H (j(ni ,|Ji |−1)) , . . . , H (j(ni ,|Ji |−mi +1)) ,

(15)

where
n
e (j(ni ,`)) (ni ) ≥ br +|J |−`+1
mi = max m ∈ [|Ji |] : Λ
i
i

for all

o
` = |Ji | − m + 1, . . . , |Ji | ,

and set ri+1 = ri + mi . Otherwise set ri+1 = ri .
e (j) (ni ) ≤ ac +1 for some j ∈ Ji ,
(b) If the lower boundary in (14) was crossed, that is, if Λ
i
0
then accept the mi ≥ 1 null hypotheses
0

H (j(ni ,1)) , H (j(ni ,2)) , . . . , H (j(ni ,mi )) ,
where
n
e (j(ni ,`)) (ni ) ≤ ac +`
m0i = max m ∈ [|Ji |] : Λ
i

for all

o
` = 1, . . . , m ,

and set ci+1 = ci + m0i . Otherwise set ci+1 = ci .
4. Stop if there are no remaining active hypotheses, i.e., if ri+1 + ci+1 = J. Otherwise, let
Ji+1 be the indices of the remaining active hypotheses and continue on to stage i + 1.
In other words, the procedure samples all active data streams until at least one of the
active null hypotheses can be accepted or rejected, indicated by the stopping rule (14). At
that point, stepdown rejection/acceptance rules are used in steps 3a/3b to reject/accept some
active null hypotheses. After updating the list of active hypotheses, the process is repeated
until no active hypotheses remain.
Remark 3.1. We make a few remarks about the generic procedure’s definition.
(A) The relationships (8)-(11) insure that there will never be a conflict between the rejections
in Step (3a) and the acceptances in Step (3b).

7

e (j)
(B) Ties in the order statistics Λ
n in Step 2 can be broken arbitrarily (at random, say)
without affecting any of the error control properties proved below in Theorems 3.1 and
3.2.
(j)

(j 0 )

(C) If common critical values can be used for all data streams, that is, if Aw = Aw = Aw
(j)
(j 0 )
and Bw = Bw = Bw for all j, j 0 , w ∈ [J], then the standardizing functions can be
dispensed with, i.e., we can take ϕ(j) (x) = x giving aj = Aj and bj = Bj for all j ∈ [J].
(j)

(j)

(D) The critical values Aw , Bw may also depend on the current sample size n of the test
statistic Λ(j) (n) being compared with them, with only notational changes in the definition
of the generic procedure and the properties proved below; to avoid overly cumbersome
notation we have omitted this from the presentation. Standard group sequential stopping boundaries – such as Pocock, O’Brien-Fleming, power family, and any others (see
Jennison and Turnbull, 2000, Chapters 2 and 4) – can be utilized for the individual test
statistics in this way.
(E) Note that the stopping time ni of the ith stage, given by (14), is determined by the
numbers ci and ri of null hypotheses that have been rejected and accepted, respectively,
during prior stages 1, . . . , i − 1. Therefore this stopping rule is completely determined
before the start of the ith stage and, in particular, unambiguously defined.
Example. Before getting to specific examples of the generic stepdown procedure, we give
a simplistic example to show the mechanics of the procedure. The following is a summary of an
example appearing in Bartroff and Song (2014b, page 104), and details of the test statistics and
critical values are given there and omitted here. All that is important for our purposes here
is that there are J = 3 chosen data streams, null/alternative hypothesis pairs (H (j) , G(j) ),
(j)
(j 0 )
and sequential test statistics Λ(j) (n) with common critical values Aw = Aw = Aw and
(j)
(j 0 )
Bw = Bw = Bw for all j, j 0 , w ∈ {1, 2, 3}, which are given in the header of Table 1. In
e (j) (n) = Λ(j) (n) in the
particular, per Remark C above we take aj = Aj , bj = Bj , and Λ
definition of the procedure. Table 1 contains three simulated sample paths and the critical
values are given in the table’s header. Let us focus on how the critical values determine the
procedure’s decisions to stop or continue sampling. The values of the stopped test statistics
are given in bold in the table.
On sample path 1, sampling proceeds until time n1 = 7 when H (1) and H (2) are rejected
because this is the first time any of the 3 test statistics exceed B1 or fall below A1 . In
particular, H (1) is rejected because Λ(1) (7) = 2.03 ≥ B1 = 1.93 and H (2) is also rejected at
this time because Λ(2) (7) = 2.03 ≥ B2 = 1.53 and one null hypothesis (i.e., H (1) ) has already
been rejected; the fact that Λ(2) (7) also exceeds B1 was not necessary for rejecting H (2) . Next,
sampling of stream 3 is continued until time n2 = 10 when H (3) is accepted because its test
statistic falls below A1 = −2.43. Similarly, on sample path 2, after rejecting H (1) at time
n1 = 7, H (2) is then rejected at time n2 = 8 because Λ(2) (8) exceeds B2 = 1.53 and one null
hypothesis (i.e., H (1) ) has already been rejected. H (3) is also accepted at time n2 = 8 for the
same reason as above. On sample path 3, all three null hypotheses are rejected at time n1 = 7
because Λ(1) (7) = 2.03 ≥ B1 , Λ(2) (7) = 2.03 ≥ B2 and one null hypothesis (i.e., H (1) ) has
already been rejected, and Λ(3) (7) = 1.22 ≥ B3 and two null hypotheses (i.e., H (1) and H (2) )
have already been rejected.

8

Table 1: Three sample paths of a stepdown procedure for J = 3 hypotheses using critical values
A1 = −2.34, A2 = −1.94, A3 = −1.27, B1 = 1.93, B2 = 1.53, B3 = .86. The values of the stopped
sequential statistics are in bold. From Bartroff and Song (2014b, page 104).
Data
Stream
(1)

1
2
3

Xn
Λ(1) (n)
(2)
Xn
Λ(2) (n)
(3)
Xn
Λ(3) (n)

1
2
3

1
2
3

3.1.2

n=1

2

0
-.41
1
.41
0
-.41

1
.00
0
.00
1
.00

0
-.41
1
.41
0
-.41

1
.00
0
.00
1
.00

1
.41
1
.41
0
-.41

0
.00
1
.81
1
.00

3

4
Sample
1
1
.41 .81
1
1
.41 .81
0
0
-.41 -.81
Sample
1
1
.41 .81
0
1
-.41 .00
0
0
-.41 -.81
Sample
1
1
.41 .81
1
0
1.22 .81
0
1
-.41 .00

5
Path 1
1
1.22
1
1.22
1
-.41
Path 2
1
1.22
1
.41
0
-1.22
Path 3
1
1.22
1
1.22
1
.41

6

7

8

9

10

1
1.62
1
1.62
0
-.81

1
2.03
1
2.03
0
-1.22

0
-1.62

0
-2.03

0
-2.43

1
1.62
1
.81
0
-1.62

1
2.03
1
1.22
0
-2.03

1
1.62
0
-2.43

1
1.62
1
1.62
1
.81

1
2.03
1
2.03
1
1.22

A Stepdown Procedure Controlling γ1 -FDP and γ2 -FNP

The following step values1 were proposed by Romano and Shaikh (2006a). For v ∈ [J] and
γ ∈ [0, 1) define
j(t, v, γ) = min{J, J + t − v, dt/γe − 1} for t ∈ [bγJc + 1],




γ(J − v)
t(v, γ) = min bγJc + 1, v,
+1 ,
1−γ
1

See Remark 3.3.

9

(16)
(17)

omitting the third term in the minimum in (16) if γ = 0. Given a nondecreasing sequence
0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1, for v ∈ [J] and γ ∈ [0, 1) define
ε(t, v, γ, {δj }) = δj(t,v,γ)

for t ∈ [bγJc + 1],

t(v,γ)

S1 (v, γ, {δj }) = v

X εt − εt−1
t

where

εt = ε(t, v, γ, {δj })

and ε0 = 0,

t=1

D1 (γ, {δj }) = max S1 (v, γ, {δj }).
0≤v≤J

These quantities also depend on the total number J of null hypotheses but we have suppressed
this in the notation since J is fixed throughout.
Theorem 3.1. Fix α, β ∈ (0, 1) and γ1 , γ2 ∈ [0, 1). Given any sequences of constants 0 ≤
δ1 ≤ . . . ≤ δJ ≤ 1 and 0 ≤ η1 ≤ . . . ≤ ηJ ≤ 1, define
αj =

αδj
,
D1 (γ1 , {δj 0 })

βj =

βηj
,
D1 (γ2 , {ηj 0 })

j ∈ [J].

(18)

If the test statistics and critical values satisfy the assumptions in Section 2.2 for these {αj , βj }j∈[J] ,
then the sequential stepdown procedure with step values (18) satisfies
γ1 -FDP(θ) ≤ α

and

γ2 -FNP(θ) ≤ β

for all

θ∈Θ

regardless of the dependence between data streams.
Remark 3.2. A special case of the theorem that will likely be useful in practice is given by
δj =

bγ1 jc + 1
,
J + bγ1 jc + 1 − j

ηj =

bγ2 jc + 1
,
J + bγ2 jc + 1 − j

j ∈ [J].

(19)

Of course there are other possibilities, such as δj = ηj = j/J, which give step values proportional to the ones used in the original FDR-controlling procedure of Benjamini and Hochberg
(1995), although Romano and Shaikh (2006a, p. 44) found these to be smaller (and thus less
desirable) than the step values (18) given by (19), for the most part.
Remark 3.3. The third term in (17) is a slight improvement over the corresponding third term
in Romano and Shaikh (2006a, Equation (3.11)), and our proof holds in their fixed sample size
setting, giving a slightly improved upper bound for the number of true hypotheses.

3.1.3

A Stepdown Procedure Controlling the k1 -FWER1 and k2 -FWER2

The stepdown procedure in the following theorem utilizes step values proposed by Lehmann
and Romano (2005).
Theorem 3.2. Fix α, β ∈ (0, 1), k1 , k2 ∈ [J], and define
αj =

k1 α
,
J − (j − k1 )+

βj =

k2 β
,
J − (j − k2 )+

j ∈ [J],

(20)

where x+ = max{x, 0}. If the test statistics and critical values satisfy the assumptions in
Section 2.2 for these {αj , βj }j∈[J] , then the sequential stepdown procedure with step values
(20) satisfies
k1 -FWER1 (θ) ≤ α

and

k2 -FWER2 (θ) ≤ β

regardless of the dependence between data streams.

10

for all

θ∈Θ

(21)

Remark 3.4. Lehmann and Romano (2005, Theorem 2.3) exhibit a distribution of fixed sample
size p-values for which the achieved (type I) FWER is exactly the prescribed value α. The fixed
(j)
sample size setting being a special case of the sequential setup considered here (by taking X1
(j)
in (1) to be the fixed sample size data and Xn = ∅ for n > 1), applying their example to both
true and false null hypotheses shows that there is a distribution for the data such that both the
inequalities in (21) are equalities. In this sense the bounds (21) are sharp.

3.2

Stepup Procedures

In this section we develop stepup procedures analogously to what was done for stepdown
procedures in Section 3.1.

3.2.1

The Generic Sequential Stepup Procedure

Here we define a generic sequential stepup procedure, special cases of which will be used to
define the type I and II k-FWER and γ-FDP controlling sequential procedures below. We
assume that step values {αj , βj }j∈[J] satisfying (5) are given and that the test statistics and
critical values satisfy the assumptions in Section 2.2 with respect to these values.
As for the generic sequential stepdown procedure in Section 3.1.1, we describe the stepup
procedure in terms of stages of sampling, between which reject/accept decisions are made, and
we use the same notation Ji , ni , ri , and ci as there, with J1 = [J], n0 = 0, and r1 = c1 = 0.
Then the ith stage of sampling (i = 1, 2, . . .) of the Generic Sequential Stepup Procedure
with step values {αj , βj }j∈[J] proceeds as follows.
(j)

1. Sample the active data streams {Xn }j∈Ji , n>ni−1 until n equals
n
e (j(n,`)) (n) 6∈ (ac +` , br +|J |−`+1 ) for some
ni = inf n > ni−1 : Λ
i
i
i

o
` ∈ [|Ji |] ,

(22)

where j(n, `) denotes the index of the `th ordered active standardized statistic at sample
size n.
2. (a) If an upper boundary in (22) was crossed, that is, if
e (j(ni ,`)) (ni ) ≥ br +|J |−`+1
Λ
i
i

for some

` ∈ [|Ji |],

then reject the mi ≥ 1 null hypotheses
H (j(ni ,|Ji |)) , H (j(ni ,|Ji |−1)) , . . . , H (j(ni ,|Ji |−mi +1)) ,
where

n
o
e (j(ni ,|Ji |−m+1)) (ni ) ≥ br +m ,
mi = max m ∈ [|Ji |] : Λ
i

and set ri+1 = ri + mi . Otherwise set ri+1 = ri .
(b) If a lower boundary in (22) was crossed, that is, if
e (j(ni ,`)) (ni ) ≤ ac +`
Λ
i

for some

` ∈ [|Ji |],

then accept the m0i ≥ 1 null hypotheses
0

0

H (j(ni ,mi )) , H (j(ni ,mi −1)) , . . . , H (j(ni ,1)) ,
where

n
o
e (j(ni ,m)) (ni ) ≤ ac +m ,
m0i = max m ∈ [|Ji |] : Λ
i

and set ci+1 = ci + m0i . Otherwise set ci+1 = ci .

11

(23)

3. Stop if there are no remaining active hypotheses, i.e., if ri+1 + ci+1 = J. Otherwise, let
Ji+1 be the indices of the remaining active hypotheses and continue on to stage i + 1.
In other words, the procedure samples all active data streams until at least one of the
active null hypotheses can be accepted or rejected, indicated by the stopping rule (22). At
that point, stepup rejection/acceptance rules are used in steps 2a/2b to reject/accept some
active null hypotheses. After updating the list of active hypotheses, the process is repeated
until no active hypotheses remain.
Remark 3.5. Points analogous to Remark 3.1 apply to the generic sequential stepup procedure
as well.

3.2.2

A Stepup Procedure Controlling γ1 -FDP and γ2 -FNP

The following step values were proposed by Romano and Shaikh (2006b). Given a nondecreasing sequence 0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1, for γ ∈ [0, 1) and v ∈ [J] define
X

S2 (v, γ, {δj }) = vδ1 + v

v−J+1<s≤v, v≥bγ(J−v+s)c+1

δJ−v+s − δJ−v+s−1
,
s ∨ (bγ(J − v + s)c + 1)

D2 (γ, {δj }) = max S2 (v, γ, {δj }).
v∈[J]

Here x ∨ y = max{x, y}. These quantities also depend on J but we have suppressed this in
the notation since J is fixed throughout.
Theorem 3.3. Fix α, β ∈ (0, 1) and γ1 , γ2 ∈ [0, 1). Given any sequences of constants 0 ≤
δ1 ≤ . . . ≤ δJ ≤ 1 and 0 ≤ η1 ≤ . . . ≤ ηJ ≤ 1, define
αj =

αδj
,
D2 (γ1 , {δj 0 })

βj =

βηj
,
D2 (γ2 , {ηj 0 })

j ∈ [J].

(24)

If the test statistics and critical values satisfy the assumptions in Section 2.2 for these {αj , βj }j∈[J] ,
then the sequential stepup procedure with step values (24) satisfies
γ1 -FDP(θ) ≤ α

and

γ2 -FNP(θ) ≤ β

for all

θ∈Θ

regardless of the dependence between data streams.
Remark 3.6. A special case of the theorem that will likely be useful in practice is given by
(19). Of course there are other possibilities, such as δj = ηj = j/J, which give step values
proportional to the ones used in the original FDR-controlling procedure of Benjamini and
Hochberg (1995), although Romano and Shaikh (2006b, p. 1865) found these to be smaller
(and thus less desirable), for the most part, than the step values (24) given by (19).
Remark 3.7. Romano and Shaikh (2006a, Theorem 4.1(ii)) exhibit a joint distribution of
p-values under which the procedure using step values (25) achieves γ1 -FDP(θ) = α. Since, as
mentioned in Remark 3.4, the fixed-sample setting is a special case of the sequential setting,
their example applies here as well, and the same argument gives a joint distribution under
which γ2 -FNP = β. Thus, their result provides a weak optimality property of the sequential
stepup procedure.

12

3.2.3

A Stepup Procedure Controlling k1 -FWER1 and k2 -FWER2

The following step values were proposed by Romano and Shaikh (2006b). Given a nondecreasing sequence 0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1, for k, v ∈ [J] define
S3 (v, k, {δj }) =

X δJ−v+s − δJ−v+s−1
vδJ−v+k
+v
,
k
s
k<s≤v

D3 (k, {δj }) = max S3 (v, k, {δj }).
k≤v≤J

These quantities also depend on J but we have suppressed this in the notation since J is fixed
throughout.
Theorem 3.4. Fix α, β ∈ (0, 1) and k1 , k2 ∈ [J]. Given any sequences of constants 0 ≤ δ1 ≤
. . . ≤ δJ ≤ 1 and 0 ≤ η1 ≤ . . . ≤ ηJ ≤ 1, define
αj =

αδj
,
D3 (k1 , {δj 0 })

βj =

βηj
,
D3 (k2 , {ηj 0 })

j ∈ [J].

(25)

If the test statistics and critical values satisfy the assumptions in Section 2.2 for these {αj , βj }j∈[J] ,
then the sequential stepup procedure with step values (25) satisfies
k1 -FWER1 (θ) ≤ α

and

k2 -FWER2 (θ) ≤ β

for all

θ∈Θ

regardless of the dependence between data streams.
Remark 3.8. A special case of the theorem that will likely be useful in practice is given by the
constants
k1
k2
δj =
, ηj =
, j ∈ [J],
(26)
+
J − (j − k1 )
J − (j − k2 )+
which are proportional to those proposed by Hommel and Hoffmann (1988) and Lehmann and
Romano (2005), as well as (20) in the proposed stepdown procedure. Other possibilities exist,
such as δj = ηj = j/J, but Romano and Shaikh (2006b, p. 1859) computed the resulting step
values (25) for both of these choices and found that those given by (26) to be larger (and hence
more desirable) than those given by j/J for large or small values of j, and smaller for moderate
values of j but differing by relatively little in this case.
Remark 3.9. Romano and Shaikh (2006b, Theorem 3.1(ii)) exhibited a joint distribution of
p-values under which the procedure using step values (25) achieves k1 -FWER1 (θ) = α. Since,
as mentioned in Remark 3.4, the fixed-sample setting is a special case of the sequential setting,
their example applies here as well, and the same argument gives a joint distribution under which
k2 -FWER2 (θ) = β. Thus, their result provides a weak optimality property of the sequential
stepup procedure.

4 Versions of the Procedures Controlling only the
Type I Generalized Error Rate
In this section we describe versions of the above procedures which only stop early to reject
(rather than accept) null hypotheses and thus which only explicitly control the corresponding
type I generalized error rate, recorded in Theorems 4.1 and 4.2. For this reason we refer to
them as “rejective” versions of the procedures. The rejective procedures may be preferable to

13

the statistician in certain situations such as when (a) a null hypothesis being true represents the
system being “in control” and therefore continued sampling (rather than stopping) is desirable,
(b) there is a maximum sample size imposed on the data streams preventing achievement of
the error bounds (6)-(7), or (c) the type II generalized error rate β is not well-motivated.
In any of theses cases, the statistician may prefer to drop the requirement that the type II
generalized error rate be strictly controlled at β and use one of the rejective procedures which,
(j)
roughly speaking, are similar to those above but ignore the lower stopping boundaries Aw .
However, even if β is not well motivated but the statistician prefers early stopping under
the null hypotheses, then we encourage the use of the procedures above while treating β as
a parameter to be chosen to give a procedure with other desirable operating characteristics,
such as expected total or streamwise maximum sample size.
The setup for rejective procedures is similar to that above with a few modifications. Let
(j)
the data streams Xn , test statistics Λ(j) (n), and parameters θ(j) and θ be as in Section 2.
Since only the type I error rate, i.e., γ1 -FDP or k1 -FWER1 , will be explicitly controlled we
only require specification of null hypotheses H (j) ⊆ Θ(j) and not alternative hypotheses G(j) .
Accordingly we modify the definition of the false hypotheses (3) to be
F(θ) = {j ∈ [J] : θ(j) 6∈ H (j) },
and the true hypotheses T (θ) are still given by (2). As mentioned in point (b) above, one
situation in which the rejective procedures may be be desirable is when there is a streamwise
maximum sample size (or “truncation point”) N which we now assume in this section, although
with only notational changes what follows could be formulated without a truncation point or
with sample sizes other than 1, . . . , N .
Given a sequence of step values 0 ≤ α1 ≤ . . . ≤ αJ ≤ 1, we assume that the test statis(j)
(j)
tics Λ(j) (n) have associated critical values B1 , . . . , BJ satisfying


(j)
Pθ(j) Λ(j) (n) ≥ Bw
for some n ≤ N ≤ αw for all θ(j) ∈ H (j) ,
(27)
for each w ∈ [J], as well as (8) and (10) without loss of generality. We let the standardizing
(j)
functions ϕ(j) be any increasing functions such that bw = ϕ(j) (Bw ) does not depend on j, and
e (j) (n) = ϕ(j) (Λ(j) (n)) denote the standardized statistics.
Λ
In the next two sections we give the rejective versions of the generic stepdown and stepup
procedures in Sections 3.1.1 and 3.2.1, respectively, and state their type I generalized error
control properties in Theorems 4.1 and 4.2. The proofs are similar to the proofs of the corresponding theorems in Section 3 and are thus omitted.

4.1

Rejective Sequential Stepdown Procedures

Letting x ∧ y = min{x, y} and with the same notation as in Section 3.1.1, the ith stage
(i = 1, 2, . . .) of the Generic Rejective Sequential Stepdown Procedure with step values
{αj }j∈[J] proceeds as follows.
(j)

1. Sample the active streams {Xn }j∈Ji , n>ni−1 until n equals
n
e (j) (n) ≥ br +1 for some
ni = N ∧ inf n > ni−1 : Λ
i

o
j ∈ Ji .

(28)

2. If ni = N and no test statistic has crossed the critical value in (28), accept all active null
hypotheses and terminate the procedure. Otherwise, proceed to Step 3.

14

3. Order the active test statistics
e (j(ni ,1)) (ni ) ≤ Λ
e (j(ni ,2)) (ni ) ≤ . . . ≤ Λ
e (j(ni ,|Ji |)) (ni )
Λ
and reject the mi ≥ 1 null hypotheses
H (j(ni ,|Ji |)) , H (j(ni ,|Ji |−1)) , . . . , H (j(ni ,|Ji |−mi +1)) ,
where
n
e (j(ni ,`)) (ni ) ≥ br +|J |−`+1
mi = max m ∈ [|Ji |] : Λ
i
i

for all

o
` = |Ji | − m + 1, . . . , |Ji | .

4. If ri + mi = J or ni = N , terminate the procedure. Otherwise, set ri+1 = ri + mi , let
Ji+1 be the indices of the remaining hypotheses, and continue on to stage i + 1.
Remark 4.1. Points analogous to Remark 3.1 (except Point A which doesn’t apply since there
is no early acceptance rule) apply to the generic rejective sequential stepdown procedure as well.
Theorem 4.1. Fix α ∈ (0, 1).
1. Fix γ1 ∈ [0, 1). Given any sequence of constants 0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1 let αj be
given by (18). If the test statistics and critical values satisfy the assumptions above for
these αj , then the rejective sequential stepdown procedure with step values (18) satisfies
γ1 -FDP(θ) ≤ α regardless of the dependence between data streams.
2. Fix k1 ∈ [J] and let αj be given by (20). If the test statistics and critical values satisfy
the assumptions above for these αj , then the rejective sequential stepdown procedure with
step values (20) satisfies k1 -FWER1 (θ) ≤ α regardless of the dependence between data
streams.
Remark 4.2. As mentioned in Remark 3.2, the δj given in (19) may be useful in practice for
the procedure in Part 1 of the theorem. Also, the weak optimality mentioned in Remark 3.4
applies as well to the rejective procedure in Part 2 of the theorem.

4.2

Rejective Sequential Stepup Procedures

With the same notation as in Section 3.2.1, the ith stage (i = 1, 2, . . .) of the Generic Rejective Sequential Stepup Procedure with step values {αj }j∈[J] proceeds as follows.
(j)

1. Sample the active data streams {Xn }j∈Ji , n>ni−1 until n equals
n
e (j(n,`)) (n) ≥ br +|J |−`+1 for some
ni = N ∧ inf n > ni−1 : Λ
i
i

o
` ∈ [|Ji |] .

(29)

2. If ni = N and no test statistic has crossed its corresponding critical value in (29), accept
all active null hypotheses and terminate the procedure. Otherwise, proceed to Step 3.
3. Reject the mi ≥ 1 null hypotheses
H (j(ni ,|Ji |−mi +1)) , H (j(ni ,|Ji |−mi +2)) , . . . H (j(ni ,|Ji |)) ,
where

n
o
e (j(ni ,|Ji |−m+1)) (ni ) ≥ br +m .
mi = max m ∈ [|Ji |] : Λ
i

15

4. If ri + mi = J or ni = N , terminate the procedure. Otherwise, set ri+1 = ri + mi , let
Ji+1 be the indices of the remaining hypotheses, and continue on to stage i + 1.
Remark 4.3. Points analogous to Remark 3.1 (except Point A which doesn’t apply since there
is no early acceptance rule) apply to the generic rejective sequential stepup procedure as well.
Theorem 4.2. Fix α ∈ (0, 1).
1. Fix γ1 ∈ [0, 1). Given any sequence of constants 0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1 let αj be
given by (24). If the test statistics and critical values satisfy the assumptions above for
these αj , then the rejective sequential stepup procedure with step values (24) satisfies
γ1 -FDP(θ) ≤ α regardless of the dependence between data streams.
2. Fix k1 ∈ [J]. Given any sequence of constants 0 ≤ δ1 ≤ . . . ≤ δJ ≤ 1 let αj be
given by (25). If the test statistics and critical values satisfy the assumptions above
for these αj , then the rejective sequential stepup procedure with step values (25) satisfies
k1 -FWER1 (θ) ≤ α regardless of the dependence between data streams.
Remark 4.4. As mentioned in Remarks 3.6 and 3.8, the δj given in (19) and (26) may be
useful in practice for the procedures in Parts 1 and 2 of the theorem, respectively. Also, the
weak optimality mentioned in Remarks 3.7 and 3.9 applies as well to the rejective procedures
in Parts 1 and 2 of the theorem, respectively.

5
5.1

Implementation
Simple vs. Simple Hypotheses

In this section we briefly discuss constructing individual test statistics and critical values satisfying (6)-(7) (or (27) for the rejective versions of the procedures). More complete discussions,
including discussion of testing more general composite hypotheses and examples, are given
in Bartroff and Song (2014a,b). Here we focus on simple hypotheses and those that can be
approximated by simple hypotheses and in Theorem 5.1 we give closed-form expressions for
(j)
(j)
the critical values Aw , Bw satisfying (6)-(7) to a very close approximation, and which are
based on the closed-form, widely-used Wald approximations for the sequential probability ratio
test (SPRT). Sequential test statistics and critical values for other testing situations, including
composite hypotheses and nuisance parameter problems, are covered in the two papers above
and more generally in the texts Bartroff et al. (2013) and Siegmund (1985).
Focusing on a stream j for which H (j) and G(j) are simple hypotheses, a natural choice for
the test statistic Λ(j) (n) is the log-likelihood ratio because of its strong optimality property of
the resulting (single hypothesis) test, the SPRT; see Chernoff (1972). In order to express the
likelihood ratio test in a simple form, we now make the additional assumption that each data
(j)
(j)
stream X1 , X2 , . . . constitutes independent and identically distributed data. However, we
stress that this independence assumption is limited to within each stream so that, for example,
(j)
(j)
elements of X1 , X2 , . . . may be correlated with (or even identical to) elements of another
(j 0 )
(j 0 )
stream X1 , X2 , . . .. Formally we represent the simple null and alternative hypotheses H (j)
and G(j) by the corresponding distinct density functions h(j) (null) and g (j) (alternative) with
respect to some common σ-finite measure µ(j) . The parameter space Θ(j) corresponding to
this data stream is the set of all densities f with respect to µ(j) , and H (j) is considered true
if the actual density f (j) satisfies f (j) = h(j) µ(j) -a.s., and is false if f (j) = g (j) µ(j) -a.s. The
SPRT for testing H (j) : f (j) = h(j) vs. G(j) : f (j) = g (j) with type I and II error probabilities

16

α and β, respectively, utilizes the simple log-likelihood ratio test statistic
!
n
(j) (X (j) )
X
g
i
Λ(j) (n) =
log
(j) (X (j) )
h
i=1
i

(30)

and samples sequentially until Λ(j) (n) 6∈ (A, B), where the critical values A, B satisfy
Ph(j) (Λ(j) (n) ≥ B some n, Λ(j) (n0 ) > A all n0 < n) ≤ α
Pg(j) (Λ

(j)

(j)

(n) ≤ A some n, Λ

(31)

0

(n ) < B all n0 < n) ≤ β.

(32)

The most simple and widely-used method for finding A and B is to use the closed-form Waldapproximations A = AW (α, β) and B = BW (α, β), where




b
1−b
AW (a, b) = log
+ ρ, BW (a, b) = log
−ρ
(33)
1−a
a
for a, b ∈ (0, 1) such that a + b ≤ 1 and a fixed quantity ρ ≥ 0. See Hoel et al. (1971,
Section 3.3.1) for a derivation of the ρ = 0 case and, based on Brownian motion approximations,
Siegmund (1985, p. 50 and Chapter X) derives the value ρ = .583 which has been used
to improve the approximation for continuous random variables. Although, in general, the
inequalities in (31)-(32) only hold approximately when using the Wald approximations A =
AW (α, β) and B = BW (α, β), Hoel et al. (1971) show that the actual type I and II error
probabilities can only exceed α or β by a small amount in the worst case, and the difference
approaches 0 for small α and β, which is relevant in the present multiple testing situation
where we will utilize small values of α and β, i.e., certain fractions of the actual prescribed
error rates.
(j)
(j)
Next we use the Wald approximations to construct closed-form critical values Aw , Bw
satisfying (6)-(7) up to Wald’s approximation. Specifically, given step values {αj , βj }, we show
that when using (34), the left-hand-sides of (6)-(7) equal the same quantities one would get
using Wald’s approximations with αj , βj in place of α, β. This generalizes results of Bartroff
and Song (2014a,b) which gave Wald approximations for the specific step values {αj , βj }
proposed for the FWER- and FDR-controlling procedures, respectively, given there.
Theorem 5.1. Fix {αj , βj }j∈[J] satisfying (5) and α1 + β1 ≤ 1, and ρ ≥ 0. Suppose that,
for a certain data stream j, the associated hypotheses H (j) : f (j) = h(j) and G(j) : f (j) = g (j)
(j)
(j)
are simple. For a, b ∈ (0, 1) such that a + b ≤ 1 let αW (a, b) and βW (a, b) be the values of
the probabilities on the left-hand sides of (31) and (32), respectively, when Λ(j) (n) is given by
(30) and A = AW (a, b) and B = BW (a, b) are given by the Wald approximations (33). For
w ∈ [J] let
α1 (1 − βw )
β1 (1 − αw )
α
ew =
and βew =
,
1 − β1
1 − α1
(j)

(j)

(j)

(j)

and let pw and qw denote the left-hand-sides of (6) and (7), respectively, with Aw , Bw
given by




βw (1 − β1 )
1 − α1 − β1 (1 − αw )
(j)
(j)
+ ρ, Bw = log
− ρ.
(34)
Aw = log
1 − β1 − α1 (1 − βw )
αw (1 − α1 )
Then, for all w ∈ [J],
αw + βew ≤ 1,
(j)

e
p(j)
w = αW (αw , βw ),

α
ew + βw ≤ 1,

(35)

(j)

(36)

and

(j)
qw
= βW (e
αw , βw )

and therefore (6)-(7) hold, up to Wald’s approximation, when using the critical values (34).

17

We remark that the ρ = 0 case of Theorem 5.1 holds without the independence assumption
(j)
(j)
on X1 , X2 , . . . made in this section, since this original form of Wald’s approximations does
not require this.

5.2

Group Sequential Testing

As mentioned above, the setup considered here is general enough to admit group sequential
sampling as a special case and the popular methods for choosing group sequential stopping
boundaries – such as Pocock’s (1977) test and O’Brien and Fleming’s (1979) test, which we
consider as examples here – can be utilized. See also Jennison and Turnbull (2000, Chapters 2.4
and 2.5) for these tests, whose setup we follow. Both Pocock’s and O’Brien and Fleming’s
tests, in their original forms, utilize a fixed maximum number g of groups and only allow early
stopping to reject the corresponding null hypothesis; if the null is not rejected at or before the
gth group then it is accepted. This is precisely the form of the rejective procedures defined in
Section 4, which we now consider; the last paragraph in this section discusses group sequential
tests that allow early rejection or acceptance of the null hypothesis. To utilize Pocock’s test of
the null hypothesis H (j) : θ(j) = 0 about the average difference θ(j) in treatment effects with
at most g groups all of size m (although groups of unequal sizes can be handled with only
(j)
(j)
(j)
(j)
minor notational burden), let Xn = (D(n−1)m+1 , D(n−1)m+2 , . . . , Dnm ), n ∈ [g], be the vector
(j)

of observed differences Di

in the nth group. Pocock’s test statistic can be written

Λ(j) (n) = √

nm
X

1
nmσ 2

(j)

Di

for n ∈ [g],

(37)

i=1

(j)

where σ 2 is the known variance of the Di . Given α ∈ (0, 1), the α-level version of the test
stops after group n ∈ [g] and rejects H (j) if Λ(j) (n) ≥ CP (α), accepting H (j) if no rejection has
occurred by the gth group. Here CP (α) is a constant (the subscript P for Pocock) calculated
to make the type I error probability of this test no greater than α, i.e.,


(38)
Pθ(j) =0 Λ(j) (n) ≥ CP (α) for some n ∈ [g] ≤ α for any α ∈ (0, 1).
Calculation of CP (α) is well-understood and included in many standard software packages; see
Jennison and Turnbull (2000, Chapter 19).
To utilize the Pocock test as the jth component test in a rejective sequential stepup or
stepdown procedure defined in Section 4, let N = g, Λ(j) (n) be as in (37) for n ∈ [g], and
(j)
Bw = CP (αw ) for w ∈ [J] where αw are the given step values. By these definitions and those
of the rejective procedures we see that H (j) will be rejected at the first stage n ∈ [N ] = [g]
(j)
where Λ(j) (n) crosses a certain boundary Bw , and accepted otherwise. All that remains to
check that Theorems 4.1 and 4.2 are in force is to verify that (27) holds, whose left-hand side
is equal to


Pθ(j) =0 Λ(j) (n) ≥ CP (αw ) for some n ∈ [g]
which, by (38), is no greater than αw .
O’Brien and Fleming’s test can be applied similarly but with the slightly different test
statistic
nm
X
1
(j)
(j)
Di
for n ∈ [g],
(39)
Λ (n) = p
2
gmσ i=1

18

p
which differs from (37) by a factor of g/n. This test stops to reject H (j) at the earliest
stage n ∈ [g] such that Λ(j) (n) ≥ COF (α), constants satisfying


Pθ(j) =0 Λ(j) (n) ≥ COF (α) for some n ∈ [g] ≤ α for any α ∈ (0, 1).
(40)
Using this test as a component test in a rejective procedure is similar to that for Pocock’s
(j)
test but taking Bw = COF (αw ). As above, (40) guarantees that (27) holds, and hence
Theorems 4.1 and 4.2 are in force.
Neither Pocock’s nor O’Brien and Fleming’s tests stop early to accept the null hypothesis,
but other popular group sequential tests do allow this behavior, such as power family tests (see
Jennison and Turnbull, 2000, Chapter 5). These tests can be used as component tests in the
sequential stepup or stepdown procedures in Section 3 in a similar way as the discussion above
for rejective procedures with the minor notational burden of including a maximum sample size
N , equal to the maximum number of groups in this group sequential setting. Of course the
choice of N , as well as the group size (e.g., m in the discussion above) may affect the ability to
achieve the needed type I and II error probabilities (6) and (7), but this issue is not unique to
multiple testing considerations and must be considered in group sequential testing of a single
null hypothesis as well.

6
6.1

Numerical Comparisons
Introduction and Setup

Although a comprehensive comparison of the sequential stepup and stepdown procedures proposed above is beyond the scope of this article, in this section we give a comparison in the
particular setting of inference about the means of strongly positively correlated Gaussian data
streams; Müller et al. (2007) note that this setting is still one of the most widely used in
applications involving multiple testing.
As mentioned in Section 2.2, if a fixed sample stepup procedure uses the same (or larger)
step values {αj } as a stepdown procedure, then the stepup procedure is preferred because it will
reject more null hypotheses and hence be more powerful while not exceeding the prescribed
multiple testing error bound α. The same statement holds about the rejective sequential
procedures in Section 4, and an analogous statement holds about the sequential procedures in
Section 3 which control both type I and II generalized error rates and their step values {αj , βj }
in which case “more powerful” means less conservative type I and II error control below
the prescribed values α and β. However there is no such simple “dominating” relationship
between the values of the stepup and stepdown procedures proposed above. For example,
Figure 1 contains plots of the stepdown versus stepup values αj defined in Sections 3.1 and
3.2, respectively, for α = .05, J = 500 null hypotheses, and γ1 = .1 for FDP control (left
panel) and k1 = 25 for k1 -FWER1 control (right panel). In both panels the solid line is below
the dotted identity line indicating that each stepdown value exceeds its corresponding stepup
value.
Thus, to investigate the efficiency and overall performance of the proposed sequential stepdown and stepup procedures, simulation studies were performed to estimate their operating
characteristics. For this, J streams of Gaussian data were repeatedly simulated in order to
consider a battery of tests of the form
H (j) : θ(j) ≤ 0

vs.

19

G(j) : θ(j) ≥ 1

(41)

0.00

0.02

Stepup values

0.010
0.005
0.000

Stepup values

0.04

k−FWER control

0.015

FDP control

0.000

0.005

0.010

0.015

0.00

Stepdown values

0.02

0.04

Stepdown values

Figure 1: Stepdown versus stepup values (solid lines) for testing J = 500 null hypotheses with
α = .05. In the left panel, the stepdown and stepup values αj are given by (18) and (24), respectively,
both with δj given by (19) and γ1 = 0.1. In the right panel, the stepdown and stepup values αj
are given by (20) and (25), respectively, with k1 = 25 and δj given by (26) in the latter case. The
identity line is dashed.

20

about the mean θ(j) of the jth data stream. The proposed procedures, with their strict
error control regardless of dependence, will probably be most useful in settings with strongly
positively correlated data streams. For example, about multiple testing problems which arise
in genetic association studies by comparing many possible statistical models for genetic data,
Zheng et al. (2012, p. 24) remark that typically “all genetic models under consideration are
positively correlated.” And in randomized multi-arm clinical trials, Freidlin et al. (2008,
p. 4369) note that “individual comparisons are positively correlated due to the use of the
same control arm.” To create such a setting of strongly positively correlated data streams, the
(1)
(J)
collection (Xn , . . . , Xn ) of the nth observations from the J data streams were simulated as a
J-dimensional multivariate normal distribution with mean θ = (θ(1) , . . . , θ(J) ) and covariance
matrix


1 .95 · · · .95
 .95 1 · · · .95 


σ2  .
(42)
.. . .
..  .
.
 .
. . 
.
.95 .95 · · · 1
Constant correlation models such as this have recently been popular in the study of genetic
correlation structure (Lee et al., 2011; Hardin et al., 2013), and for us (42) provides a convenient way of generating a large number of data streams with strong positive correlation. In
the studies that follow we have chosen σ = 2 to give tests of reasonable length. We note that,
(1)
(J)
while the collection (Xn , . . . , Xn ) of the nth observations was generated using the above
(1)
(J)
(1)
(J)
distribution, successive observations (Xn , . . . , Xn ), (Xn+1 , . . . , Xn+1 ) were generated independently. The test statistics (30) were used with θ(j) = 0 vs. θ(j) = 1 as surrogate hypotheses,
reducing to
!
n
X
1
n
(j)
Λ(j) (n) = 2
Xi −
σ
2
i=1

in this case, and the critical values (34) were used with ρ = .583 and {αj , βj } as described below. The results of simulation studies in this setting are reported in Section 6.2 for γ1 -FDP and
γ2 -FNP control, and Section 6.3 for k1 -FWER1 and k2 -FWER2 control. Finally, in Section 6.4,
the assumption of known variance is dropped and Student’s t-tests of composite hypotheses
are considered.

6.2

Study of Procedures Controlling γ1 -FDP and γ2 -FNP

Table 2 contains some operating characteristics under various settings of the sequential stepdown and stepup procedures, denoted SeqD and SeqU , defined in Sections 3.1.2 and 3.2.2
using step values (18) and (24) (both with δj given by (19)), respectively, and which control
γ1 -FDP ≤ α = .05 and γ2 -FNP ≤ β = .2. The operating characteristics are the expected
streamwise
PJ average sample size Eθ N which is the average sample size over the J streams (i.e.,
N =
j=1 Nj /J if Nj denotes the sample size of the jth stream), its standard error SE,
and the achieved generalized error rates γ1 -FDP and γ2 -FNP. Each operating characteristic
estimate is the result of 10,000 Monte Carlo simulated ensembles of J data streams. The
parameter values γ1 = γ2 = .1 were used and three states of nature, in terms of the number
of true null hypotheses H (j) , are considered for both of the J = 500 and J = 1000 scenarios,
with the true H (j) are simulated using θ(j) = 0 and the false H (j) with θ(j) = 1, representing
the “worst case” with respect to distinguishability of the null and alternative hypotheses.
In order to provide a point of reference for these sequential procedures, the performance
of comparable fixed sample size stepdown and stepup procedures, denoted by FixD and FixU ,

21

were also estimated. These are the procedures defined in Section 2.2 which use the same
step values αj as SeqD and SeqU , respectively. Since these values αj determine the type I
generalized error rate γ1 -FDP, in order to obtain procedures comparable to the sequential
ones, the fixed sample sizes for FixD and FixU were chosen as the values yielding the type II
generalized error rate γ2 -FNP most closely matching that of the sequential procedure with the
smallest Eθ N (i.e., the more efficient of SeqD and SeqU ), whose row is shaded in each scenario
in the table. Regarding this method of choosing the fixed sample size, one might argue that
a different comparison would be better since the procedures are quite conservative in their
error control, however the fixed sample size procedures are also very conservative, in fact more
conservative than the sequential procedures since the error probabilities tend to decrease as
sample size increases; in this sense the comparison is actually conservative. Because the sample
sizes of FixD and FixU are fixed, their SE is left blank. The final column of the table shows
that savings in Eθ N of each sequential procedure relative to its fixed sample counterpart.
The sequential procedures in Table 2 show a dramatic savings in average sample size relative
to the fixed sample size procedures, at least 50% in all cases and as high as 65%. The sequential
procedures also have less conservative error control than their fixed sample size counterparts,
most evident in the type I generalized error rate γ1 -FDP which was not used for “matching”
the fixed sample procedures as the type II version was. This less conservative error control
is perhaps due to the sequential procedures’ smaller average sample size. Nonetheless, all
the procedures still have quite conservative error control relative to the prescribed values of
α = .05 and β = .2 even on this highly positively correlated data. Another notable feature
of the results in Table 2 is that the sequential stepup procedures are slightly but consistently
more efficient than the stepdown procedures in each scenario, in terms of minimizing Eθ N . In
the next section we will see that the reverse is true in a similar study of procedures controlling
k1 -FWER1 and k2 -FWER2 .
Because of the highly conservative error control of all the procedures in Table 2, but
especially the fixed sample size procedures, another type of comparison that may shed light on
how much of the efficiency gained by the sequential procedures is due the sequential sampling
itself rather than the differing achieved error rates, included in the first scenario of Table 2
are two more fixed sample size procedures (denoted Fix0D and Fix0U ) which match both error
rates γ1 -FDP and γ2 -FNP of SeqD and SeqU , respectively. These were found by exhaustively
searching over values of the fixed streamwise sample size N and a grid of values for the nominal
γ1 -FDP rate α for Fix0D and Fix0U . The procedure Fix0D uses α = .092 and N = 129 to match
the error rates γ1 -FDP = .007 and γ2 -FNP = .015 of SeqD , and Fix0U uses α = .112 and
N = 110 to match γ1 -FDP = .008 and γ2 -FNP = .012 of SeqU . The increase in nominal
α required for this matching is roughly a factor of 2, and the decrease in sample size is
modest, leaving the sample sizes of Fix0D and Fix0U still substantially larger than their sequential
counterparts even though they do not have proven error control at the α = .05 level. This
suggests the efficiency gains of the sequential procedures relative to the fixed sample size
procedures are due more to the sequential sampling than their less conservative error control.

6.3

Study of Procedures Controlling k1 -FWER1 and k2 -FWER2

Table 3 contains the results of a study similar to Table 2 but for procedures controlling
k1 -FWER1 and k2 -FWER2 . In Table 3, SeqD and SeqU denote the stepdown and stepup
procedures defined in Sections 3.1.2 and 3.2.2 using step values (20) and (25), respectively,
with δj given by (26) for the latter. The parameters k1 = k2 = 25 were used for the J = 500
scenario and k1 = k2 = 50 for the J = 1000 scenario, and the same prescribed error bounds
α = .05, β = .2 were used. The operating characteristics and simulation settings are other-

22

wise the same as the previous section. As there, the stepdown and stepup fixed sample size
procedures FixD and FixU are those defined in Section 2.2 which use the same step values αj
as SeqD and SeqU , respectively, and the fixed sample sizes of these procedures was chosen to
match their type II generalized error rate k2 -FWER2 as closely as possible to the sequential
procedure with the smallest Eθ N , whose row is shaded in the table in each scenario.
Similar to the results in Table 2, the sequential procedures in Table 3 show a substantial
savings of roughly 50% to 60% in average sample size relative to the fixed sample size procedures, and less conservative error control than their fixed sample size counterparts, most
evident in the type I generalized error rate k1 -FWER1 which was not used for “matching” the
fixed sample procedures as the type II version was. All the procedures have quite conservative
error control relative to the prescribed values of α = .05 and β = .2. Unlike Table 2, the
sequential stepdown procedures in Table 3 were more efficient than the stepup procedures in
terms of smaller Eθ N .
Similar to Table 2, the first scenario in Table 3 also includes fixed sample size procedures
0
FixD and Fix0U whose values of streamwise sample size N and nominal k1 -FWER1 bound α
were searched over to find values giving attained k1 -FWER1 and k2 -FWER2 equal to those
of the sequential procedures SeqD and SeqU , respectively. The procedure Fix0D uses α = .048
and N = 77 to match the error rates k1 -FWER1 = .020 and k2 -FWER2 = .039 of SeqD , and
Fix0U uses α = .080 and N = 95 to match k1 -FWER1 = .009 and k2 -FWER2 = .034 of SeqU .
Whereas Fix0U uses a slightly smaller sample size (and larger α) than FixU because the latter
is more conservative than SeqU in terms of error rates, Fix0D uses a slightly larger sample size
(and smaller α) than FixD because the latter is actually less conservative than SeqD . In any
case, the change in sample size of these modified fixed sample procedures is slight and the
fixed sample sizes remain substantially larger than their sequential counterparts, indicating
that the increased efficiency is due to the sequential sampling rather than differing achieved
error rates, as in Table 2.

6.4

Composite Hypotheses: Student’s t-tests

In this section we consider a setting similar to the Gaussian mean testing problem (41) of the
previous sections but drop the assumption of known variance σ 2 , making both the null and
alternative in (41) composite hypotheses. First we briefly describe a sequential approach to
this Student’s t-test problem and then give the results of a simulation study in a similar setting
to Section 6.3 for k1 -FWER1 and k2 -FWER2 control.
(j)
(j)
Suppose that the data X1 , X2 , . . . from a certain data stream are i.i.d. Gaussian data
with mean µ and variance σ 2 , both unknown, and it is desired to test the null hypothesis µ ≤ 0
versus the alternative µ ≥ δ, for some given δ > 0. Formally, this is a special case of the setup
in Section 2 by taking θ(j) = (µ, σ)T , Θ(j) = R × (0, ∞), H (j) = {(µ, σ)T ∈ Θ(j) : µ ≤ 0}, and
G(j) = {(µ, σ)T ∈ Θ(j) : µ ≥ δ}. Bartroff and Song (2014b, Section 3.2) suggest sequential log
generalized likelihood ratio (GLR) statistics for a general class of composite hypotheses when
the data is from an exponential family, including this t-test setting for which the sequential
log GLR statistic is (see Bartroff, 2006, p. 106)
( p
(j)
+ 2nΛH (n), if X n ≥ δ/2
(j)
p
Λ (n) =
(43)
− 2nΛG (n), otherwise,


! 
!2 
(j) 2
(j)
n
Xn
 , ΛG (n) = n log 1 + X n − δ  ,
where ΛH (n) = log 1 +
2
σ
bn
2
σ
bn

23

(j)

(j)

(j)

and X n and σ
bn2 are the usual MLE estimates of µ and σ 2 , respectively, based on X1 , . . . , Xn .
Bartroff and Song (2014b, Lemma 3.1) also give formulas for certain upper bounds on the
probabilities in (6)-(7) involving only properties of the standard normal distribution, allow(j)
(j)
ing critical values {Aw , Bw }w∈[J] to be computed satisfying (6)-(7) for given step values
{αw , βw }w∈[J] by either recursive numerical integration or Monte Carlo simulation of standard
normal variates.
Table 4 contains the results of a study similar to Table 3 but for sequential and fixed sample
size t-tests. In Table 4, SeqD and SeqU denote the stepdown and stepup procedures defined in
Sections 3.1.2 and 3.2.2 using step values (20) and (25), respectively, with δj given by (26) for
the latter. The sequential procedures use the statistics (43) with critical values computed by
Monte Carlo as described in the previous paragraph. The stepdown and stepup fixed sample
size procedures FixD and FixU are those defined in the first paragraph of Section 2.2 with
(j) √
σn ), where
p-values for sample size n computed in the standard way as 1 − Tn−1 (X n n − 1/b
Tn−1 (·) denotes the c.d.f. of the Student’s t distribution with n − 1 degrees of freedom, and
which use the same step values αj as SeqD and SeqU , respectively. As in Section 6.3, the
fixed sample sizes of these procedures was chosen to match their type II generalized error rate
k2 -FWER2 as closely as possible to the sequential procedure with the smallest Eθ N , whose row
is shaded in the table in each scenario. To give a view of the procedures’ performance under
a different dependency structure for the Gaussian data streams, unlike the previous sections
they were simulated not as highly correlated but rather nearly independent with correlation
coefficient .05 replacing .95 in (42). The data was simulated using the same value σ = 2 as
above, but not assumed to be known.
Comparing Table 4 with the first half of Table 3, one sees that the additional task of
estimating the unknown variance in the t-test setting, plus the near-independence of the data
streams, only cause a modest increase in sample size of all the procedures. The relationship
between the sequential and fixed sample size procedures is otherwise remarkably similar to that
in Table 3, with the stepdown procedure SeqD being slightly more efficient than the stepup
procedure SeqU for FWER control, and both being roughly 50-60% more efficient than the
fixed sample size procedures in terms of expected sample size. Also like Table 3, all procedures
are very conservative in terms of error control, with the sequential procedures tending to be
less so (but not uniformly – see FixD in the case of 400 true H (j) ) because of their smaller
average sample size.

7

Conclusions and Discussion

We have proposed general and flexible multiple testing procedures for controlling generalized
error rates on sequential data whose error control holds regardless of dependence between
data streams. We have given both stepdown and stepup procedures for controlling the tail
probabilities of FDP and k-FWER, as well as their type II versions, but in the numerical
studies of their performance in Section 6 in the setting of highly positively correlated Gaussian
data streams we found that, in terms of achieving smaller expected sample size,
• the stepup procedures performed better for controlling FDP, and
• the stepdown procedures performed better for controlling k-FWER.
Although this study was limited to the specific setting of testing hypotheses about the means
of Gaussian data streams with covariance matrix (42), these are our working recommendations
for what to use in practice until further study is possible.

24

The same simulation studies also show the procedures to be highly conservative in the
situation considered, in terms of having generalized error rates substantially smaller than the
prescribed values α and β. However, it is apparent that this is not related to the sequential
nature of the procedures proposed here because the fixed sample versions also have this property and even more so. This is not surprising since the error rates tend to decrease as sample
size increases and efficient sequential procedures will have smaller expected sample sizes than
their fixed sample counterparts. On the other hand, the results of Lehmann and Romano
(2005) and Romano and Shaikh (2006a) (repeated above in Remarks 3.4, 3.7, and 3.9) show
that the error bounds are indeed “sharp” and cannot be improved without more restrictive
assumptions on the joint distribution of the data streams. However, less conservative error
control (or equivalently, more efficiency in terms of smaller expected sample sizes) may be
possible by assumptions about (or direct modeling of) this joint distribution, which was not
the focus of this paper but may be a fruitful area of future work.
As mentioned above,
The procedures proposed above, as well as those in Bartroff and Song (2014a,b) for
FDR/FNR and type I/II FWER control, are all special cases of the generic sequential procedures in Sections 3.1.1 and 3.2.1 and all use the same step values as the corresponding fixed
sample size procedures: the Bartroff and Song (2014a,b) procedures utilize the same step values as the Benjamini and Hochberg (1995) and Holm (1979) procedures, respectively, and the
procedures in this paper utilize the step values of Lehmann and Romano (2005) and Romano
and Shaikh (2006a,b). Thus, the theme that emerges from this body of work is that, with the
appropriate care, fixed sample size step values can be used with the suitable sequential test.

8

Proofs and Auxiliary Results

The proofs of the error-control properties of both the stepup and stepdown procedures utilize
the following, as well as Lemma 8.1 that follows. Let
n
o
e (j) (n) ≥ b for some n, Λ
e (j) (n0 ) > a1 for all n0 < n ,
W (j, b) = Λ
(44)
Vθ (t, b) =

t
\

[

W (j` , b),

(45)

Pθ(j) (W (j, b)),

(46)

j1 ,...,jt ∈T (θ) `=1

p(j) (b) =

sup
θ(j) ∈H (j)

Mθ (b) =

X

1W (j,b) .

(47)

j∈T (θ)

The union in (45) is over all distinct t-tuples j1 , . . . , jt ∈ T (θ). The event W (j, b) is that
the standardized test statistic associated with the jth null hypothesis crosses b from below
before crossing a1 from above, and Vθ (t, b) is the event that there are at least t true null
hypotheses for which this occurs. The function p(j) (b) is the “worst-case” (with respect to the
null) probability of W (j, b) happening, and the random variable Mθ (b) is the number of true
null hypotheses for which this occurs. Note that any test statistic satisfying the assumptions
in Section 2.2, in particular (12), satisfies p(j) (bw ) ≤ αw for all j, w ∈ [J]. Note also that the
events W (j, ·) are non-increasing in the sense that, for any j ∈ [J],
b ≤ b0

implies

W (j, b0 ) ⊆ W (j, b).

It follows from this property that the events Vθ (t, ·) are non-increasing, and that Mθ (·) is nonincreasing with probability 1. It can also be easily verified that Vθ (·, b) are non-increasing. In

25

what follows we will frequently drop the θ from Vθ , Mθ , and other quantities when it causes
no confusion.
The following lemma is an extension to the sequential domain of Lehmann and Romano
(2005, Lemma 3.1).
Lemma 8.1. In the testing situation above, fix θ ∈ Θ such that T (θ) is nonempty, let t =
|T (θ)| ∈ [J], t0 ∈ [t], and let 0 = ζ0 ≤ . . . ≤ ζt0 ≤ 1 and b01 ≥ b02 ≥ . . . ≥ b0t0 be any
sequences. With p(j) (b) defined by (46), if the test statistics {Λ(j) (n)} satisfy p(j) (b0s ) ≤ ζs for
all j ∈ T (θ), s ∈ [t0 ], then with Vθ (t, b) defined by (45), we have
!
t0
t0
[
X
ζs − ζs−1
0
Pθ
Vθ (s, bs ) ≤ t
.
(48)
s
s=1

s=1

Proof of Lemma 8.1. Omit θ from the notation. With M (b) as in (47),
X
X
E(M (b0s )) =
P (W (j, b0s )) ≤
p(j) (b0s ) ≤ tζs .
j∈T

(49)

j∈T

Define the random variable
(
min{s ∈ [t0 ] : 1V (s,b0s ) = 1},
τ=
t + 1,

if 1V (s,b0s ) = 1 for some s ∈ [t0 ]
,
otherwise

and let πs = P (τ = s). Then the left-hand side of (48) is
!
t0
t0
[
X
P
{τ = s} =
πs
s=1

s=1

Pt1

by disjointness. For any t1 ∈ [t0 ] we have s=1 τ 1{τ =s} = τ 1{τ ≤t1 } ≤ M (b0t1 ) by definition of
P1
V and W . Taking expectations and using (49) gives ts=1
sπs ≤ tζt1 . Dividing both sides of
this last by t1 (t1 + 1) (resp. t1 ) for t1 = 1, . . . , t0 − 1 (resp. t0 = t1 ) and summing over t1 gives
tX
0 −1
t1 =1

t1
t0
tX
0 −1
X
1 X
tζt1
tζt
1
sπs +
sπs ≤
+ 0.
t1 (t1 + 1)
t0
t1 (t1 + 1)
t0
s=1

s=1

(50)

t1 =1

The right-hand side of (50)
P 0is easily seen to be the right-hand side of (48), while the left-hand
side of (50) simplifies to ts=1
πs after reversing the order of summation in the first term.

8.1

Proofs of Results for Stepdown Procedures in Section 3.1

Proof of Theorem 3.1. We consider the generic stepdown procedure defined in Section 3.1.1
with step values given by (18). Fix θ ∈ Θ such that T (θ) is nonempty and omit it from the
notation. We show that γ1 -FDP ≤ α, the other claim being similar. Our method of proof
here, similar to the other theorems, will be to introduce auxiliary random variables (denoted
with superscript ∗ ) describing the behavior of the specific sequential stepdown procedure under
consideration, and then establish inequalities that these random variables satisfy on the event
F = {FDP > γ1 }. In other words, the interpretation of all such inequalities should be that
they hold with P (·|F )-probability 1, where we assume without loss of generality that P (F ) > 0
since otherwise there is nothing to prove.

26

As the stepdown procedure proceeds according to its definition in Section 3.1.1, we may
think of the FDP as being updated according to its definition (4) after each rejection of a null
hypothesis. In particular, the FDP is updated mi times during the ith stage according to the
ordering (15). Considering sample paths of data streams on which FDP > γ1 (i.e., outcomes in
the event F ), we define the following auxiliary random variables: Let i∗ be the earliest stage at
which the updated FDP exceeds γ1 at some point during the stage, let m∗ denote the smallest
value of m such that the rejection of H (j(ni∗ ,|Ji∗ |−m+1)) causes the updated FDP to exceed γ1 ,
let r∗ = m∗ + mi∗ so that the r∗ th rejection causes the FDP to first exceed γ1 , and finally let
s∗ be the unique integer s satisfying s − 1 ≤ γ1 r∗ < s so that bγ1 r∗ c + 1 = s∗ . Also, define
these random variables arbitrary (equal to ∞, say) off of F so they are defined on the entire
sample space. Note that whereas the ri in the definition of the procedure in Section 3.1.1 are
only updated at the end of each stage, the value of r∗ may be determined before the end of the
corresponding stage and thus will not necessarily equal any of the ri , even for i = i∗ . Upon
the r∗ th rejection, s∗ true null hypotheses have been rejected. In other words, F ⊆ V (s∗ , br∗ ),
where
[
V (s∗ , br∗ ) =
(V (s, br ) ∩ {r∗ = r} ∩ {s∗ = s}) .
(51)
r,s

and V (s, b) is defined in (45). We note that br∗ is merely an auxiliary random variable useful for
proving γ1 -FDP control and is not necessarily equal to, say, the stopping boundary appearing
in (14) for any particular stage of the procedure.
The number |T | of true null hypotheses satisfies
|T | ≤ J − (r∗ − s∗ ).

(52)

Also, since s∗ /γ1 (interpreted as ∞ if γ1 = 0) strictly exceeds r∗ we have r∗ ≤ ds∗ /γ1 e − 1.
Denoting j(s, |T |, γ1 ) and D1 (γ1 , {δj }) simply by j(s) and D1 , respectively, these last two
bounds imply that
r∗ ≤ j(s∗ ).
(53)
Next we bound the possible values of s∗ from above. Because r∗ ≤ J we have s∗ ≤ bγ1 Jc+1,
and clearly s∗ ≤ |T |. Also, by the minimal properties of i∗ and m∗ it must be that the
previous update of the FDP, which took the value (s∗ − 1)/(r∗ − 1), did not exceed γ1 , hence
(s∗ − 1)/(r∗ − 1) ≤ γ1 , or
s∗ ≤ γ1 (r∗ − 1) + 1 ≤ γ1 (J − |T | + s∗ − 1) + 1,
using (52). Simplifying and taking the floor gives


γ1 (J − |T |)
s∗ ≤
+ 1,
1 − γ1

(54)

and combining these three bounds gives
s∗ ≤ t(|T |, γ1 ),

(55)

which we denote simply by t.
Let F1 be the event that (53) and (55) hold, and note that F ⊆ F1 by the arguments

27

leading to those inequalities. Then
t
X

∗

γ1 -FDP = P (F ) = P (F ∩ F1 ) ≤ P (V (s , br∗ ) ∩ F1 ) ≤

P (V (s0 , br∗ ) ∩ {s∗ = s0 } ∩ F1 )

s0 =1

≤

t
X

P (V (s0 , bj(s∗ ) )∩{s∗ = s0 }∩F1 )

[since (53) holds on F1 and V (s0 , ·) are non-increasing]

s0 =1

=

t
X

P (V (s0 , bj(s0 ) ) ∩ {s∗ = s0 } ∩ F1 ) ≤

s0 =1

t
X


P

s0 =1


≤P

t
[

t
[


V (s, bj(s) ) ∩ {s∗ = s0 } ∩ F1 

s=1





V (s, bj(s) ) ∩ F1  ≤ P 

s=1

t
[


V (s, bj(s) ) . (56)

s=1

The third-to-last inequality in (56) holds by expanding the event V (s0 , bj(s0 ) ) into the union
event.
Now let εs = ε(s, |T |, γ1 , {δj }) and it is not hard to verify that the εs are non-decreasing
in s. We have
αδj(s)
αεs
P (W (j, bj(s) )) ≤ αj(s) =
=
.
(57)
D1
D1
Applying Lemma 8.1 (with ζs = αεs /D1 ) to the last term in (56) gives
γ1 -FDP ≤ |T |

t
X
αj(s) − αj(s−1)
s=1

s

t

α|T | X εs − εs−1
αS
=
=
≤ α.
D1
s
D1
s=1

The proof that γ2 -FNP ≤ β is completely symmetric and there is no conflict or interaction
between rejections and acceptances of null hypotheses.

Proof of Theorem 3.2. We consider the generic stepdown procedure defined in Section 3.1.1
with step values given by (20). We will show that the procedure satisfies k1 -FWER1 (θ) ≤ α, the
other claim being similar. Fix θ ∈ Θ such that |T (θ)| ≥ k1 , since otherwise k1 -FWER1 (θ) = 0,
and omit θ from the notation. As in the proof of Theorem 3.1 we shall introduce auxiliary
random variables (denoted with superscript ∗ ) describing the behavior of the procedure and
then establish inequalities that these random variables satisfy on the event
F = {at least k1 null hypotheses H (j) rejected, j ∈ T }.
In other words, the interpretation of all such inequalities should be that they hold with P (·|F )probability 1, where we assume without loss of generality that P (F ) > 0 since otherwise there
is nothing to prove.
Considering outcomes on which at least k1 true null hypotheses are rejected (i.e., outcomes
in F ), define the following random variables: Let i∗ and m∗ be the stage and index, respectively,
∗
of the k1 th rejected true null hypothesis H (j(ni∗ ,|Ji∗ |−m +1)) , and let r∗ = m∗ + mi∗ so that the
r∗ th null hypothesis rejected is the k1 th true null hypothesis rejected. As above, define these
random variables arbitrarily off of F so they are defined on the entire sample space. Then
r∗ ≤ J − |T | + k1

28

(58)

because r∗ takes its largest possible value when the only remaining hypotheses upon the r∗ th
rejection are the |T | − k1 remaining true null hypotheses. As in the proof of Theorem 3.1, r∗
may be determined before the end of stage i∗ and should not be confused with the ri in the
definition of the procedure in Section 3.1.1.
With M (b) as in (47), note that M (br∗ ) ≥ k1 on F since at least k1 standardized test statistics corresponding to true nulls must cross br∗ before crossing the furthest lower boundary a1 ,
since otherwise a null would be accepted rather than rejected by definition of the stepdown
procedure. Thus F ⊆ {M (br∗ ) ≥ k1 } and so
M (br∗ ) ≤ M (bJ−|T |+k1 )

(59)

by (58) and the monotonicity of M (·) and the bj . Then, using (59) and Markov’s inequality,

1
k1 -FWER1 = P (F ) ≤ P (M (br∗ ) ≥ k1 ) ≤ P (M (bJ−|T |+k1 ) ≥ k1 ) ≤ E M (bJ−|T |+k1 )
k1


X
1
1 X
1 X
= E
1W (j,bJ−|T |+k )  =
P (W (j, bJ−|T |+k1 )) ≤
αJ−|T |+k1
1
k1
k1
k1
j∈T

j∈T

j∈T

=

8.2

|T |αJ−|T |+k1
= α.
k1

Proofs of Results for Stepup Procedures in Section 3.2

The proofs of both Theorems 3.3 and 3.4 utilize the following lemma.
Lemma 8.2. For the generic sequential stepup procedure in Section 3.2.1, under θ ∈ Θ, for
any s ∈ [J] we have
{exactly s null hypotheses rejected } ⊆ Vθ (t∗ , bs ),

(60)

the latter defined as
Vθ (t∗ , bs ) =

[

(Vθ (t, bs ) ∩ {t∗ = t})

(61)

t

where Vθ (t, b) is as in (45) and t∗ is the number of true null hypotheses rejected.
Proof. Let R(s) denote the event on the left-hand side of (60). On outcomes in R(s) define
the following random variables: Let i∗ be the stage at which the sth rejection occurs, let j ∗
∗
be such that H (j ) is the sth rejected null hypothesis, and recall that t∗ is the number of
∗
true hypotheses rejected. By definition of H (j ) and by step 2a of the procedure we have
e (j ∗ ) (ni∗ ) ≥ br ∗ +m ∗ . If a true hypothesis H (j 0 ) ,
j ∗ = j(ni∗ , |Ji∗ | − mi∗ + 1), s = ri∗ + mi∗ , and Λ
i
i
j 0 ∈ T , is rejected then it is rejected at some stage i0 ≤ i∗ , and j 0 = j(ni0 , `) for some
` ≥ |Ji0 | − mi0 + 1. Note that ri0 + mi0 ≤ s because if i0 = i∗ then ri0 + mi0 = ri∗ + mi∗ = s,
and otherwise i0 ≤ i∗ − 1 so ri0 + mi0 = ri0 +1 ≤ ri∗ ≤ s. Then
e (j 0 ) (ni0 ) = Λ
e (j(ni0 ,`)) (ni0 ) ≥ Λ
e (j(ni0 ,|Ji0 |−mi0 +1)) (ni0 ) ≥ br 0 +m 0 ≥ bs ,
Λ
i
i
using (23) for the second-to-last inequality. This holds for any rejected true hypothesis, hence
there are distinct j1 , . . . , jt∗ ∈ T such that, for each ` ∈ [t∗ ], H (j` ) is rejected and
e (j` ) (n) ≥ bs
Λ

29

for some n.

(62)

(j )

e 0` ≤ a1 for some n0 less than the corresponding n in (62), then H (j` ) would not
If it were that Λ
n
have been rejected but rather accepted, contradicting our assumption about H (j` ) . Combining
these statements gives that any outcome in R(s) is in V (t∗ , bs ).
Proof of Theorem 3.3. We consider the generic stepup procedure defined in Section 3.2.1 with
step values given by (24). Fix θ ∈ Θ such that T (θ) is nonempty, and omit θ from the notation.
We will show that γ1 -FDP ≤ α, the other claim being similar. For s ∈ [J] let γ(s) = bγ1 sc + 1
and let T (s) denote the event that at least γ(s) true null hypotheses are rejected, and let R(s)
be the event on the left-hand side of (60). We claim that
(
V (γ(s) ∨ (s + |T | − J), bs ), if γ(s) ≤ |T |,
R(s) ∩ T (s) ⊆
(63)
∅,
otherwise.
By Lemma 8.2 we have R(s) ∩ T (s) ⊆ V (t∗ , bs ) ∩ T (s), and to finish the proof of (63) we show
that, on any outcome in the latter event, defined analogously to (61), t∗ ≥ γ(s) ∨ (s + |T | − J)
if s is such that γ(s) ≤ |T | and then use that V (·, b) is non-increasing; the other case of
(63) is trivial by the definition of R(s) and T (s). We recall that this and other inequalities
involving the random variable t∗ should be interpreted as holding with P (·|V (t∗ , bs ) ∩ T (s))probability 1, this event assumed without loss of generality to have positive probability. We
know that t∗ ≥ γ(s) by definition of T (s). On the other hand, t∗ is equal to the number s of
null hypotheses rejected minus the number of false null hypotheses rejected, the latter bounded
above by J − |T |, hence t∗ ≥ s + |T | − J.
With (63) established we have
[
[
γ1 -FDP =
R(s) ∩ T (s) ⊆
V (γ(s) ∨ (s + |T | − J), bs )
1≤s≤J

1≤s≤J, γ(s)≤|T |

[

=

V (γ(J + s − |T |) ∨ s, bJ+s−|T | ). (64)

|T |−J+1≤s≤|T |, γ(J+s−|T |)≤|T |

For s in the range of the union in (64), let σ(s) = γ(J + s − |T |) ∨ s, which is a non-decreasing
sequence of consecutive integers taking the values 1, 2, . . . , s1 for some s1 ≤ |T | by virtue of
the restrictions in (64). For s ∈ [s1 ] let σ −1 (s) = max{s0 : σ(s0 ) = s}. If σ(s) = σ(s + 1) then
using the non-increasing property of V (s, ·) we have
V (σ(s), bJ+s−|T | ) ∪ V (σ(s + 1), bJ+s+1−|T | ) ⊆ V (σ(s + 1), bJ+s+1−|T | ).

(65)

By collapsing terms in (64) according to (65), we have that the union in (64) is contained in
s1
[

V (s, bJ+σ−1 (s)−|T | ).

s=1

Denote S2 (|T |, γ1 , {δj }) and D2 (γ1 , {δj }) by S2 and D2 , respectively. Applying Lemma 8.1 to
this last with ζs = αJ+σ−1 (s)−|T | and b0s = bJ+σ−1 (s)−|T | , and recalling that s1 ≤ |T |, we have
!
s1
[
D2
D2
· P (FDP > γ1 ) ≤
·P
V (s, bJ+σ−1 (s)−|T | )
|T |α
|T |α
s=1


X
α
−
α
−1
−1
D2
J+σ (s)−|T |
J+σ (s−1)−|T | 
≤
· |T | αJ+σ−1 (1)−|T | +
|T |α
s
1<s≤s1

= δJ+σ−1 (1)−|T | +

X δJ+σ−1 (s)−|T | − δJ+σ−1 (s−1)−|T |
. (66)
s

1<s≤s1

30

We claim that (66) is equal to
X

S2 /|T | = δ1 +

|T |−J+1<s≤|T |, |T |≥bγ1 (J−|T |+s)c+1

δJ−|T |+s − δJ−|T |+s−1
,
s ∨ (bγ1 (J − |T | + s)c + 1)

(67)

which would complete the proof since S2 ≤ D2 . Note that the denominator in (67) is σ(s). If
σ −1 (1) = |T | − J + 1 then the first term in both (66) and (67) is δ1 . Otherwise, σ −1 (1) = s2 >
|T | − J + 1, and the first J + s2 − |T | summands in (67) are
δ1 +

δJ+s2 −|T | − δJ+s2 −|T |−1
δ2 − δ1
+ ... +
σ(|T | − J + 2)
σ(s2 )
δJ+s2 −|T | − δJ+s2 −|T |−1
δ2 − δ1
+ ... +
= δJ+s2 −|T | ,
= δ1 +
1
1

which is the first summand in (66) in this case. Proceeding in this way one may verify the
claim term by term, completing the proof.

Proof of Theorem 3.4. We consider the generic stepup procedure defined in Section 3.2.1 with
step values given by (25). We will show that the procedure satisfies k1 -FWER1 (θ) ≤ α, the
other claim being similar. Fix θ ∈ Θ such that |T (θ)| ≥ k1 , since otherwise k1 -FWER1 (θ) = 0,
and omit θ from the notation. For s ∈ [J] let T (s) denote the event that at least k1 true null
hypotheses are rejected and let R(s) be the event on the left-hand side of (60). We claim that
R(s) ∩ T (s) ⊆ V (k1 ∨ (s + |T | − J), bs )

for all

s ∈ [J].

(68)

By Lemma 8.2 we have R(s)∩T (s) ⊆ V (t∗ , bs )∩T (s), the latter defined analogously to (61), and
to finish the proof of (68) we show that, on any outcome in the latter event, t∗ ≥ k1 ∨(s+|T |−J)
and use that V (·, b) is non-increasing. We recall that this and other inequalities involving the
random variable t∗ should be interpreted as holding with P (·|V (t∗ , bs )∩T (s))-probability 1, this
event assumed without loss of generality to have positive probability. We know that t∗ ≥ k1 by
definition of T (s). On the other hand, t∗ is equal to the number s of null hypotheses rejected
minus the number of false null hypotheses rejected, the latter bounded above by J − |T |, hence
t∗ ≥ s + |T | − J.
With (68) established we have
[
[
R(s) ∩ T (s) ⊆
V (k1 ∨ (s + |T | − J), bs )
(69)
k1 ≤s≤J

k1 ≤s≤J




 

 

[
=
V (k1 , bs ) ∪
V (s + |T | − J, bs )

 

k1 ≤s≤J−|T |+k1
J−|T |+k1 <s≤J




[
V (s + |T | − J, bs )
(70)
⊆ V (k1 , bJ−|T |+k1 ) ∪


J−|T |+k1 <s≤J
[
[
=
V (s + |T | − J, bs ) =
V (s, b|T |−J+s ),
(71)
[

J−|T |+k1 ≤s≤J

k1 ≤s≤|T |

where the inclusion in (70) follows from the facts that bs ≥ bJ−|T |+k1 for s ≤ J −|T |+k1 and the
V (k1 , ·) are non-increasing. The k1 -FWER1 is the probability of the event on the left-hand side
of (69), and applying Lemma 8.1 to the last union in (71) with t0 = |T |, ζ0 = . . . = ζk1 −1 = 0,

31

ζs = α|T |−J+s for k1 ≤ s ≤ |T |, b01 = . . . = b0k1 −1 = ∞, and b0s = b|T |−J+s for k1 ≤ s ≤ |T |, we
have


X
α|T |−J+k1
α|T |−J+s − α|T |−J+s−1

k1 -FWER1 ≤ |T | 
+
k1
s
k1 <s≤|T |


α
S3 (k1 , |T |, {δj }) ≤ α.
=
D3 (k1 , {δj })

8.3

Proof of Theorem 5.1

We verify the first parts of (35) and (36); the other parts are similar. We have
−(1 − αw )(1 − α1 − β1 )
β1 (1 − αw )
−1+1=
+ 1 ≤ 1,
0 ≤ αw + βew = αw +
1 − α1
1 − α1
(j)

using α1 + β1 ≤ 1 for the last inequality. It is simple algebra to check that Bw in (34) can be
(j)
written as BW (αw , βew ), and A1 in (34) can be written as AW (αw , βew ) for any w ∈ [J]. Then
(j)

(j)
(j)
(j) 0
0
p(j)
w = Ph(j) (Λ (n) ≥ Bw some n, Λ (n ) > A1 all n < n)
= Ph(j) (Λ(j) (n) ≥ BW (αw , βew ) some n, Λ(j) (n0 ) > AW (αw , βew ) all n0 < n)
(j)
= αW (αw , βew ),
(j)

by definition of αW .

References
Baillie, D. (1987). Multivariate acceptance sampling – some applications to defence procurement. Journal of the Royal Statistical Society, Series D (The Statistician), 36(5):465–478.
Bartroff, J. (2006). Efficient three-stage t-tests. In Recent Developments in Nonparametric
Inference and Probability: Festschrift for Michael Woodroofe, volume 50 of IMS Lecture
Notes Monograph Series, pages 105–111, Hayward. Institute of Mathematical Statistics.
Bartroff, J. and Lai, T. L. (2010). Multistage tests of multiple hypotheses. Communications
in Statistics – Theory and Methods (Special Issue Honoring M. Akahira, M. Aoshima, ed.),
39:1597–1607.
Bartroff, J., Lai, T. L., and Shih, M. (2013). Sequential Experimentation in Clinical Trials:
Design and Analysis. Springer, New York.
Bartroff, J. and Song, J. (2014a). Sequential tests of multiple hypotheses controlling false
discovery and nondiscovery rates. Under review. https://arxiv.org/abs/1311.3350
Bartroff, J. and Song, J. (2014b). Sequential tests of multiple hypotheses controlling type I
and II familywise error rates. Journal of Statistical Planning and Inference, 153:100–114.

32

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:289–300.
Benjamini, Y. and Yekutieli, D. (2001). The control of the false discovery rate in multiple
testing under dependency. The Annals of Statistics, 29(4):1165–1188.
Chernoff, H. (1972). Sequential Analysis and Optimal Design. Society for Industrial and
Applied Mathematics, Philadelphia.
Clements, N., Sarkar, S. K., Zhao, Z., and Kim, D.-Y. (2014). Applying multiple testing
procedures to detect change in East African vegetation. The Annals of Applied Statistics,
8:286–308.
De, S. and Baron, M. (2012a). Sequential Bonferroni methods for multiple hypothesis testing
with strong control of family-wise error rates I and II. Sequential Analysis, 31(2):238–262.
De, S. and Baron, M. (2012b). Step-up and step-down methods for testing multiple hypotheses
in sequential experiments. Journal of Statistical Planning and Inference, 142:2059–2070.
Freidlin, B., Korn, E. L., Gray, R., and Martin, A. (2008). Multi-arm clinical trials of new
agents: Some design considerations. Clinical Cancer Research, 14(14):4368–4371.
Guo, W., He, L., and Sarkar, S. K. (2014). Further results on controlling the false discovery
proportion. The Annals of Statistics, 42(3):1070–1101.
Hardin, J., Garcia, S. R., and Golan, D. (2013). A method for generating realistic correlation
matrices. The Annals of Applied Statistics, 7(3):1733–1762.
Hoel, P. G., Port, S. C., and Stone, C. J. (1971). Introduction to Statistical Theory. Houghton
Mifflin Co., Boston, Mass.
Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal
of Statistics, 6:65–70.
Hommel, G. and Hoffmann, T. (1988). Controlled uncertainty. In Bauer, P., Hommel, G., and
Sonnemann, E., editors, Multiple Hypothesenprüfung/Multiple Hypotheses Testing, pages
154–161. Springer, Heidelberg.
Jennison, C. and Turnbull, B. W. (2000). Group Sequential Methods with Applications to
Clinical Trials. Chapman & Hall/CRC, New York.
Jiang, H. and Salzman, J. (2012). Statistical properties of an early stopping rule for resamplingbased multiple testing. Biometrika, 99(4):973–980.
Lai, T. L. and Xing, H. (2008). Statistical Models and Methods for Financial Markets. Springer,
New York.
Lee, S. H., Wray, N. R., Goddard, M. E., and Visscher, P. M. (2011). Estimating missing
heritability for disease from genome-wide association studies. The American Journal of
Human Genetics, 88(3):294–305.
Lehmann, E. L. and Romano, J. P. (2005). Generalizations of the familywise error rate. The
Annals of Statistics, 33(3):1138–1154.

33

Mei, Y. (2010). Efficient scalable schemes for monitoring a large number of data streams.
Biometrika, 97(2):419–433.
Müller, P., Parmigiani, G., and Rice, K. (2007). FDR and Bayesian multiple comparisons
rules. In Bernardo, J. M., Bayarri, M. J., Berger, J. O., Dawid, A. P., Heckerman, D.,
Smith, A. F. M., and West, M., editors, Bayesian Statistics 8: Proceedings of the Eighth
Valencia International Meeting, June 2-6, 2006, pages 349–370. Oxford University Press.
O’Brien, P. C. and Fleming, T. R. (1979). A multiple testing procedure for clinical trials.
Biometrics, 35:549–556.
Pocock, S. J. (1977). Group sequential methods in the design and analysis of clinical trials.
Biometrika, 64(2):191–199.
Romano, J. P. and Shaikh, A. M. (2006a). On stepdown control of the false discovery proportion. In Rojo, J., editor, Optimality: The Second Erich L. Lehmann Symposium, volume 49
of IMS Lecture Notes–Monograph Series, pages 33–50, Beachwood, Ohio, USA. Institute of
Mathematical Statistics.
Romano, J. P. and Shaikh, A. M. (2006b). Stepup procedures for control of generalizations of
the familywise error rate. The Annals of Statistics, 34:1850–1873.
Salzman, J., Jiang, H., and Wong, W. H. (2011). Statistical modeling of RNA-seq data.
Statistical Science, 26:62–83.
Sarkar, S. (2007). Stepup procedures controlling generalized FWER and generalized FDR.
The Annals of Statistics, 35:2405–2420.
Sarkar, S. (2008). Generalizing Simes’ test and Hochberg’s stepup procedure. The Annals of
Statistics, 36:337–363.
Siegmund, D. (1985). Sequential Analysis: Tests and Confidence Intervals. Springer-Verlag,
New York.
Tartakovsky, A., Li, X., and Yaralov, G. (2003). Sequential detection of targets in multichannel
systems. Information Theory, IEEE Transactions on, 49(2):425–445.
Zheng, G., Yang, Y., Zhu, X., and Elston, R. (2012). Analysis of Genetic Association Studies.
Springer, New York.

34

Table 2: Expected streamwise average sample size Eθ N , its standard error SE, achieved error
rates γ1 -FDP and γ2 -FNP, and savings in Eθ N of the sequential (denoted SeqD and SeqU ) and
fixed sample size (denoted FixD and FixU ) procedures described in Section 6.2 for testing J null
hypotheses about the means of Gaussian data streams. The parameter values are α = .05, β = .2,
and γ1 = γ2 = .1 and each estimate is the result of 10,000 simulated ensembles of J data streams.
The shaded row in each scenario is the procedure with the smallest Eθ N .
# True H (j)

100

250

400

250

500

750

Procedure

Eθ N

SeqD
SeqU
FixD
FixU
Fix0D
Fix0U
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU

63.63
54.17
136
120
129
110
60.66
53.39
135
128
56.98
45.97
134
131

SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU

67.26
54.93
147
125
65.54
54.06
130
118
63.16
49.72
136
129

SE γ1 -FDP(θ) γ2 -FNP(θ)
J = 500
0.60
0.007
0.015
0.67
0.008
0.012
0.002
0.012
0.001
0.012
0.007
0.015
0.008
0.012
0.40
0.004
0.026
0.40
0.003
0.016
0.001
0.015
0.001
0.016
0.58
0.006
0.039
0.57
0.007
0.022
0.001
0.022
0.001
0.022
J = 1000
0.52
0.006
0.008
0.58
0.003
0.009
0.002
0.009
0.001
0.009
0.39
0.009
0.021
0.41
0.002
0.027
0.001
0.026
0.001
0.026
0.55
0.001
0.026
0.53
0.002
0.023
0.001
0.023
0.001
0.023

35

Eθ N Savings
53%
55%

55%
58%

57%
65%

54%
56%

50%
54%

54%
61%

Table 3: Expected streamwise average sample size Eθ N , its standard error SE, achieved error rates
k1 -FWER1 and k2 -FWER2 , and the savings in Eθ N of the sequential (denoted SeqD and SeqU )
and fixed sample size (denoted FixD and FixU ) procedures described in Section 6.3 for testing J
null hypotheses about the means of Gaussian data streams. The parameter values are α = .05 and
β = .2 and each estimate is the result of 10,000 simulated ensembles of J data streams. The shaded
row in each scenario is the procedure with the smallest Eθ N .
# True H (j)

100

250

400

250

500

750

Procedure
SeqD
SeqU
FixD
FixU
Fix0D
Fix0U
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU

Eθ N

SE k1 -FWER1 (θ) k2 -FWER2 (θ)
J = 500, k1 = k2 = 25
38.39 0.48
0.020
0.039
44.91 0.59
0.009
0.034
75
0.023
0.039
97
0.002
0.040
77
0.020
0.039
95
0.009
0.034
36.81 0.32
0.017
0.047
43.32 0.38
0.011
0.041
86
0.005
0.047
97
0.001
0.046
32.12 0.46
0.007
0.067
38.17 0.53
0.009
0.065
80
0.030
0.066
89
0.001
0.066
J = 1000, k1 = k2 = 50
37.45 0.42
0.015
0.033
44.07 0.51
0.005
0.042
89
0.009
0.034
100
0.002
0.034
36.73 0.31
0.012
0.050
42.46 0.38
0.008
0.044
86
0.005
0.051
96
0.001
0.049
33.27 0.41
0.012
0.065
39.93 0.46
0.006
0.040
82
0.003
0.063
92
0.001
0.064

36

Eθ N Savings
49%
54%

57%
55%

60%
57%

58%
56%

57%
56%

59%
57%

Table 4: Expected streamwise average sample size Eθ N , its standard error SE, achieved error rates
k1 -FWER1 and k2 -FWER2 , and the savings in Eθ N of the sequential (denoted SeqD and SeqU ) and
fixed sample size (denoted FixD and FixU ) procedures described in Section 6.4 for testing J null
hypotheses about the means of Gaussian data streams with unknown variances. The parameter
values are α = .05 and β = .2 and each estimate is the result of 10,000 simulated ensembles of J
data streams. The shaded row in each scenario is the procedure with the smallest Eθ N .
# True H (j)

100

250

400

Procedure

Eθ N

SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU
SeqD
SeqU
FixD
FixU

J
40.22
47.58
77
103
38.79
44.79
89
101
33.62
37.10
85
93

SE k1 -FWER1 (θ) k2 -FWER2 (θ)
= 500, k1 = k2 = 25
0.09
0.003
0.053
0.11
0.006
0.021
0.003
0.053
0.002
0.053
0.04
0.018
0.060
0.05
0.003
0.018
0.006
0.059
0.001
0.060
0.09
0.009
0.059
0.11
0.011
0.057
0.037
0.060
0.002
0.059

37

Eθ N Savings
48%
54%

56%
56%

60%
60%

