A fully sequential procedure for indifference-zone selection in simulation.
We present procedures for selecting the best or near-best of a finite number of simulated systems when best is defined by maximum or minimum expected performance. The procedures are appropriate when it is possible to repeatedly obtain small, incremental samples from each simulated system. The goal of such a sequential procedure is to eliminate, at an early stage of experimentation, those simulated systems that are apparently inferior, and thereby reduce the overall computational effort required to find the best. The procedures we present accommodate unequal variances across systems and the use of common random numbers. However, they are based on the assumption of normally distributed data, so we analyze the impact of batching (to achieve approximate normality or independence) on the performance of the procedures. Comparisons with some existing indifference-zone procedures are also provided.
Introduction
In a series of papers (Boesel and Nelson 1999, Goldsman and Nelson 1998ab, Nelson and
Banerjee 1999, Nelson and Goldsman 1998, Nelson, Swann, Goldsman and Song 1998, Miller,
Nelson and Reilly 1996, 1998ab), we have addressed the problem of selecting the best simulated
system when the number of systems is finite and no functional relationship among the
systems is assumed. We have focussed primarily on situations in which "best" is defined by
maximum or minimum expected performance, which is also the definition we adopt in the
present paper.
Our work grows out of the substantial literature on ranking, selection and multiple comparison
procedures in statistics (see, for instance, Bechhofer, Santner and Goldsman 1995,
Hochberg and Tamhane 1987, and Hsu 1996), particularly the "indifference zone" approach
in which the experimenter specifies a practically significant difference worth detecting. Our
approach has been to adapt, extend and invent procedures to account for situations and
opportunities that are common in simulation experiments, but perhaps less so in physical
experiments. These include:
ffl Unknown and unequal variances across different simulated systems.
ffl Dependence across systems' outputs due to the use of common random numbers.
ffl Dependence within a system's output when only a single replication is obtained from
each system in a "steady-state simulation."
ffl A very large number of alternatives that differ widely in performance.
ffl Alternatives that are available sequentially or in groups, rather than all at once, as
might occur in an exploratory study or within an optimization/search procedure.
Prior to the present paper, we have proposed procedures that kept the number of stages
small, say 1, 2 or 3, where a "stage" occurs whenever we initiate a simulation of a system
to obtain data. It makes sense to keep the number of stages small when they are implemented
manually by the experimenter, or when it is difficult to stop and restart simulations.
However, as simulation software makes better use of modern computing environments, the
programming difficulties in switching among alternatives to obtain increments of data are
diminishing (although there may still be substantial computing overhead incurred in making
the switch). The procedures presented in this paper can, if desired, take only a single basic
observation from each alternative still in play at each stage. For that reason they are said to
be "fully sequential." The motivation for adopting fully sequential procedures is to reduce
the overall simulation effort required to find the best system by eliminating clearly inferior
alternatives early in the experimentation.
For those situations in which there is substantial computing overhead when switching
among alternative systems, we also evaluate the benefits of taking batches of data-rather
than a single observation-from each system at each stage. These results have implications
for the steady-state simulation problem when the method of batch means is employed, or
when the simulation data are not approximately normally distributed.
Our work can be viewed as extending, in several directions, the results of Paulson (1964)
and Hartmann (1991), specifically in dealing with unequal variances across systems and dependence
across systems due to the use of common random numbers (CRN). See also Hartmann
(1988), Bechhofer, Dunnett, Goldsman and Hartmann (1990) and Jennison, Johnstone
and Turnbull (1982).
The paper is organized as follows. In Section 2 we provide an algorithm for our fully
sequential procedure and prove its validity. Section 3 provides guidance on how to choose
various design parameters of the procedure, including critical constants, batch size and
whether or not to use CRN. Some empirical results are provided in Section 4, followed
by conclusions in Section 5.
2 The Procedure
In this section we describe a fully sequential procedure that guarantees, with confidence level
greater than or equal to 1 \Gamma ff, that the system ultimately selected has the largest true mean
when the true mean of the best is at least ffi better than the second best. When there are
systems whose means are within ffi of the true best, then the procedure guarantees
to find one of these "good" systems with the same probability. The parameter ffi, which is
termed the indifference zone, is set by the experimenter to the smallest actual difference that
it is important to detect. Differences of less than ffi are considered practically insignificant.
The procedure is sequential, has the potential to eliminate alternatives from further
consideration at each stage, and terminates with only one system remaining in contention.
However, the experimenter may also choose to terminate the procedure when there are m - 1
systems still in contention, in which case the procedure guarantees that the subset of size m
contains the best system (or one of the good systems) with confidence greater than or equal
to
Throughout the paper we use the notation X ij to indicate the jth independent observation
from system i. We assume that the
unknown. Notice
may be the mean of a batch of observations, provided the batch size remains
fixed throughout the procedure (we analyze the effect of batch size later). We also let
the sample mean of the first r observations from system i. The
procedure is valid with or without the use of common random numbers.
Fully Sequential, Indifference-Zone Procedure
Select confidence level 1 \Gamma ff, indifference zone ffi and first stage sample size n 0 - 2.
Calculate j and c as described below.
Initialization: Let I = kg be the set of systems still in contention, and let h
2cj \Theta (n
from each system
For all i 6= ' compute
the sample variance of the difference between systems i and '. Let
where b\Deltac indicates truncation of any fractional part, and let
Here is the maximum number of observations that will be taken from system i.
select the system with the largest -
as the best.
and go to Screening.
Screening: Set I old = I. Let
I old and -
where
2cr
Notice that W i' (r) decreases as the number of replications r increases.
Stopping Rule: If select the system whose index is in I as the best.
Otherwise, take one additional observation X i;r+1 from each system i 2 I and set
select the system whose index is in I and has the
largest -
as the best. Otherwise go to Screening.
(Notice that the stopping rule can also be it is desired to find a subset
containing the best, rather than the single best.)
Constants: The constant c may be any nonnegative integer, with standard choices being
we evaluate different choices later in the paper and argue that
typically the best choice. The constant j is the solution to the equation
c
c
where I is the indicator function. In the special case that c = 1 we have the closed-form
solution
To prove the validity of the procedure we will need the following lemmas from Fabian
(1974) and Tamhane (1977):
Let
for some a ? 0 and fl - 0. Let R(n) denote the interval (L(n); U(n)), and let
2 R(n)g be the first time the partial sum S(n) does not fall in the triangular region
defined by R(n). Finally, let E be the event fS(T
;g. If positive integer c, then
c
Remark: In our proof that the fully sequential procedure provides the stated correct selection
guarantee, the event E will correspond to an incorrect selection (incorrectly eliminating
the best system from consideration).
independent random variables, and let
nonnegative, real-valued functions, each one nondecreasing
in each of its arguments. Then
Y
Y
Without loss of generality, suppose that the true means of the systems are indexed so
that - k - be a vector of observations
across all k systems.
Theorem 1 If are distributed i.i.d. multivariate normal with unknown mean
vector - and unknown, positive definite covariance matrix \Sigma, then with probability
the fully sequential indifference-zone procedure selects system k provided
Proof: We begin by considering the case of only 2 systems, denoted k and i, with - k - i +ffi.
Select a value of j such that
violated
Notice that T is the stage at which the procedure terminates. Let ICS denote the event that
an incorrect selection is made at time T . Then
ik
oe ik
ik
ffi2coe ik
2coe ik
oe ik
\Gammah
ik
ffi2coe ik
2coe ik
and "SC" denotes the slippage configuration -
Notice that under the SC, (X are i.i.d. N(\Delta; 1) with In lemma 1,
let
ik
ffi2coe ik
ik
ffioe ik
and \Delta=(2c). Therefore, the lemma implies that
But observe that
c
\Theta (n
ik
ik
and (n
ik has a chi-squared distribution with degrees of freedom. To evaluate
the expectation, recall that E [expft- 2
- a chi-squared
random variable with - degrees of freedom. Thus, the expected value of (4) is
c
c
where the equality follows from the way we choose j.
Thus, we have a bound on the probability of an incorrect selection when there are two
systems. Now consider k - 2 systems, set be the event that an
incorrect selection is made when systems k and i are considered in isolation. Then
ff
and the result is proven.
Remark: This procedure is valid with or without the use of common random numbers,
since the effect of CRN is to change (ideally reduce) the value of oe 2
ik , which is not important
in the proof. Notice that reducing oe 2
ik will tend to reduce S 2
ik , which narrows (by decreasing
a) and shortens (by decreasing N i ) the continuation region R(n). Thus, CRN should allow
alternatives to be eliminated earlier in the sampling process.
the fully sequential indifference-zone
procedure selects one of the systems whose mean is within ffi of - k .
then the result is trivially true, since any selected system constitutes
a correct selection.
Suppose there exists t ? 1 such that - k
Prfsystems are eliminatedg
Prfsystem k is selected from among
If we know that the systems will be simulated independently (no CRN), then it is possible
to reduce the value of j somewhat using an approach similar to Hartmann (1991); the smaller
j is the more quickly the procedure terminates. In this case we set
rather than ff=(k \Gamma 1), but otherwise leave the procedure unchanged. It is not difficult to
show that 2, and that, as a
consequence of Theorem 2.3 of Fabian (1974), g \Gamma1 (fi) is a nonincreasing function of fi.
Theorem 2 Under the same assumptions as Theorem 1, except that \Sigma is a diagonal matrix,
the fully sequential indifference-zone procedure selects system k with probability
Proof: Let CS denote the event that a correct selection is made, and CS i the event that a
correct selection is made if system i faces system k in isolation. Then
because the intersection event requires system k to eliminate each inferior system i individ-
ually, whereas in reality some system ' 6= could eliminate i. Thus,
Pr
Pr
ik
where the last equality follows because the events are conditionally independent. Clearly,
(5) does not increase if we assume the slippage configuration, so we do so from here on.
Now notice that Pr fCS
ik g is nondecreasing in X kj and S 2
ik . There-
fore, by lemma 2,
Pr
ik
ik
jo
where the last inequality follows from the proof of Theorem 1.
Remark: A corollary analogous to Corollary 1 can easily be proven in this case as well.
Key to the development of the fully sequential procedure is Fabian's (1974) result that
allows us to control the chance that we incorrectly eliminate the best system, system k,
when the partial sum process
wanders below 0. Fabian's analysis is based
on linking this partial sum process with a corresponding Brownian motion process. We are
aware of at least one other large-deviation type result that could be used for this purpose
(Robbins (1970)), and in fact is used by Swanepoel and Geertsema (1976) to derive a fully
sequential procedure. However, it is easy to show that Robbin's result leads to a continuation
region that is, in expected value, much larger than Fabian's region, implying a less efficient
procedure.
3 Design of the Procedure
In this section we examine factors that the experimenter can control in customizing the fully
sequential procedure for their problem. Specifically, we look at the choice of c, whether or
not to use CRN, and the effect of batch size. We conclude that
choice, CRN should almost always be employed, but the best batch size depends on the
relative cost of stages of sampling versus individual observations.
3.1 Choice of c
Fabian's result defines a continuation region for the partial sum process,
Provided c ! 1, this region is a triangle, and as long as the partial sum stays within this
triangle sampling continues. As c increases the triangle becomes longer, but narrower, and
in the limit becomes an open rectangle. Figure 1 shows the continuation region for our
procedure.
The type of region that is best for a particular problem will depend on characteristics of
the problem: If there is one dominant system and the others are grossly inferior, then having
the region as narrow as possible is advantageous since the inferior systems will be eliminated
quickly. However, if there are a number of very close competitors so that sampling is likely to
continue to the end stage, then a short, fat region is desirable. Of course, the experimenter
is unlikely to know such things in advance.
To compare various values of c, we propose looking at the area of the continuation region
they imply. The smallest area results from the best combination of small base-implying
that clearly inferior systems can be eliminated early in the experiment-and short height-
r

Figure

1: Continuation region for the fully sequential, indifference-zone procedure when
implying reasonable termination of the procedure if it goes to the last possible stage.
Using area as the metric immediately rules out since the area is infinite. For
the area of the continuation region is (ignoring rounding)
ik
!/
ik
ik
or simply cj 2 in units of 2(n
ik =ffi 3 . Thus, for fixed n 0 , the key quantity is cj 2 . Below
we provide numerical results that strongly suggest that
all k.

Table

1 lists the value of cj 2 for
(completely analogous results are obtained when In all of these cases
the smallest area. Therefore, when the experimenter has no idea if there are a
few dominant systems or a number of close competitors, the choice of appears to be a
good compromise solution. We set the remainder of the paper.
3.2 Common Random Numbers
As described in Section 2, the choice to use or not to use CRN alters the fully sequential
procedure only through the parameter j, which is smaller if we simulate the systems independently
(no CRN). A smaller value of j tends to make the procedure more efficient.
However, if we use CRN then we expect the value of S 2
i' to be smaller, which also tends to
make the procedure more efficient. In this section we show that even a small decrease in S 2
due to the use of CRN is enough to offset the increase in j that we incur.
Recall that the parameter j is the solution of the equation
we use CRN, while we know the systems are simulated independently.
C be the solution when CRN is employed, and let j I be the solution if the systems are
simulated independently.
For is easy to show that g(j) is nonincreasing in j ? 0; in fact, g(j) is decreasing
than or equal to 1
with equality holding only when 2. These two facts imply that j C - j I . Below we
derive a bound on j C =j I for practically useful values of k, n 0 and ff.
Ignoring rounding,
I
hi
The ratio \Psi is a function of n 0 , ff and k, and we are interested in finding an upper bound
100, the range of parameters we consider to be
of practical importance.
To accomplish this, we evaluated the @\Psi=@n 0 for all
and at narrow grid of ff values (including the standard 0:10; 0:05 and 0:01 values). For this

Table

1: Area cj 2 in units of 2(n
range, @\Psi=@n 0 is always less than zero; therefore, \Psi is a decreasing function of n 0 - 2. This
implies that we need to consider only the smallest value of n 0 to find an upper bound on (6).
After setting n the smallest value of interest to us, we observed that (6) is an
increasing function of ff by evaluating @\Psi=@ff for each k in the range of interest. Thus, the
largest ff, which is 0:1, should be chosen to find an upper bound:
Now we have only one variable remaining, k, and by evaluating (7) for all k in the range of
interest we find that gives the largest value, which is 1:01845. Therefore, we conclude
that for the practical range of interest
I
That is, j C is at most 1.02 times j I . To relate this ratio to the potential benefits of using
CRN, we consider two performance measures: the expected maximum number of replications
and the expected area on the continuation region.
Let N C and N I be the maximum number of replications and let A C and A I be the area of
the continuation region with CRN and without CRN, respectively. To simplify the analysis,
assume the variances across systems are all equal to oe 2 and that the correlation
induced between systems by CRN is ignoring rounding,
2cj I (n
I
Equation (8) shows that CRN will reduce the expected maximum number of replications if
implying that ae -
0:02 is always sufficient.
Recall that the area of the continuation region for a pair of systems i; j is given by
Under the same assumptions we can show that
I
This again implies that ae -
0:02 is always sufficient for CRN to reduce the
expected area of the continuation region. Therefore, for the range of parameters 2 - k - 100,
we claim that achieving a positive correlation of at least
0:02 is sufficient to make the use of CRN superior to simulating the systems independently.
3.3 The Effect of Batch Size
There are several reasons why an experimenter might want X ij , the jth observation from
system i, to be the mean of a batch of more basic observations:
ffl When the computing overhead for switching among simulated systems is high, it may
be computationally efficient to obtain more than one observation from each system
each time it is simulated.
ffl Even if the basic observations deviate significantly from the assumed normal distribu-
tion, batch means of these observations will be more nearly normal.
ffl If the simulation of system i involves only a single, incrementally extended, replication
of a steady-state simulation, then the basic observations may deviate significantly from
the assumed independence, while batch means of a sufficiently large number of basic
observations may be nearly independent.
In this section we investigate the effect of batch size on the fully sequential procedure. To
facilitate the analysis we assume that the total number of basic observations obtained in the
first-stage of sampling, denoted, n raw
0 , is fixed, and that all systems use a common batch size
b. However, the procedure itself does not depend on a common batch size across systems,
only that the batch size remains fixed within each system. Throughout our analysis we use
the setting in the fully sequential procedure.
a basic observation, denote the mean of a batch of b basic
observations. Let S 2
i' [b] be the sample variance of the difference between the batch means
from systems i and ', and let n
=b denote the number of batch means X ij [b] required
in the first stage of sampling. For the purpose of analysis we assume that n 0 is always integer
and that each basic observation X ij from system i is simulated independently and follows a
normal distribution with mean - i and common unknown variance oe 2 (recall that common
variance is not an assumption of our procedure). Then,
rawand
Under these conditions, if we ignore rounding
\Theta
As mentioned in Section 2, (n
i' [b] has a chi-squared distribution with
degrees of freedom, so the expected maximum number of stages involves the maximum of
identically distributed, but dependent, chi-squared variables. However, simulation
analysis of several cases revealed that the effect of this dependence on the expected value is
weak, so for the purpose of analysis we use the approximation
where f and F are the density and cdf, respectively, of the chi-square distribution with
degrees of freedom. In other words, we treat the S 2
i' [b]; ' 6= i as if they are independent.
Expression (12) is a function of k and n 0 , while j is a function of k; n 0 and ff. If we
assume that n raw
0 is given, then for any fixed k and 1 \Gamma ff the expected maximum number
normalized

Figure

2: E[N i ] as a function of number of batches n 0 when 0:95 and the
number of observations n raw
0 is fixed. For each value of k the result is normalized by dividing
by
of stages (11) depends only on the initial number of batches, n 0 , provided we express it in
units of (oe=
. Unfortunately, there is no closed-form expression for (12), but we
can evaluate it numerically.

Figure

as a function of the number of batches n 0 for different values of
k. To make the plot easier to view, the E[N i ] for each value of k is divided by E[N i ] when
batches. This figure shows that the expected maximum number of stages decreases,
then increases, as a function of the number of batches in the first stage when n raw
batches
decrease
in
number
of
raw
replications

Figure

3: Percentage decrease in E[bN i ] as a function of number of batches n 0 when
0:95 and the number of observations n raw
The savings in the beginning are caused by increasing the degrees of freedom. However,
after n 0 passes some point there is no further benefit from increased degrees of freedom, so
the effect of increasing n 0 (dividing the output into smaller batches, eventually leading to a
batch size of 1) is simply to increase the number of stages. The expected maximum number
of stages, E[N i ], is important when the computing overhead for switching among systems is
substantial.

Figure

3 shows the percentage decrease in E[bN i ], the number of basic (unbatched) ob-
servations, as the number of batches (but not the number of basic first-stage observations
increased. The expected maximum number of basic observations is important when
the cost of obtaining basic observations dominates the cost of multiple stages of sampling.
As the figure shows, this quantity is minimized by using a batch size of (that is, no
batching), but the figure also shows that once we obtain, say, 15 to 20 batches, there is little
potential reduction in E[bN i ] from increasing the number of batches (decreasing the batch
further.
For a fixed number of basic observations, the choice of number of batches n 0 should be
made considering the two criteria, E[N i ] and E[bN i ]. If the cost of switching among systems
dominates, then a small number (5 to 10) batches will tend to minimize the number of stages.
When the cost of obtaining each basic observation dominates, as it often will, then from 15
to 20 batch means are desirable at the first stage; of course, if neither nonnormality nor
dependence is a problem then a batch size of 1 will be best in this case.
4 Experiments
In this section we summarize the results of experiments performed to compare the following
procedures:
1. Rinott's (1978) procedure (RP), a two-stage indifference-zone selection procedure that
makes no attempt to eliminate systems prior to the second (and last) stage of sampling.
2. A two-stage screen-and-select procedure (2SP) proposed by Nelson, Swann, Goldsman
and Song (1998) that uses subset selection (at confidence level 1 \Gamma ff=2) to eliminate systems
after the first stage of sampling, and then applies Rinott's second-stage sampling
rule (at confidence level 1 \Gamma ff=2) to the survivors.
3. The fully sequential procedure (FSP) proposed in Section 2, both with and without
CRN (recall that the two versions differ only in the value of j used).
The systems were represented by various configurations of k normal distributions; in all
cases system 1 was the true best (had the largest true mean). We evaluated each procedure
on different variations of the systems, examining factors including the number of systems,
batch size, b; the correlation between systems, ae; the true means, and the
true variances, oe 2
k . The configurations, the experiment design, and the results are
described below.
4.1 Configurations and Experiment Design
To allow for several different batch sizes, we chose the first-stage sample size to be n raw
making batch sizes of possible. Thus, n 0 (the number of first-stage batch
means) was 24, 12 or 8, respectively. The number of systems in each experiment varied over
The indifference zone, ffi, was set to
1 is the variance of an observation
from the best system. Thus, ffi is the standard deviation of the first-stage sample
mean of the best system.
Two configurations of the true means were used: The slippage configuration (SC), in
which - 1 was set to ffi, while - This is a difficult configuration
for procedures that try to eliminate systems because all of the inferior systems are close to
the best. To investigate the effectiveness of the procedures in eliminating non-competitive
systems, monotone decreasing means (MDM) were also used. In the MDM configuration,
the means of all systems were spaced evenly apart according to the following
. Values of - were (effectively
spacing each mean 2ffi; ffi or ffi=3 from the previous mean).
For each configuration of the means we examined the effect of both equal and unequal
variances. In the equal-variance configuration oe i was set to 1. In the unequal-variance
configuration the variance of the best system was set both higher and lower than the variances
of the other systems. In the MDM configurations, experiments were run with the variance
directly proportional to the mean of each system, and inversely proportional to the mean of
each system. Specifically, oe 2
to examine the effect of increasing variance as the
mean decreases, and oe 2
to examine the effect of decreasing variances as
the mean decreases. In addition, some experiments were run with means in the SC, but with
the variances of all systems either monotonically decreasing or monotonically increasing as
in the MDM configuration.
When CRN was employed we assumed that the correlation between all pairs of systems
was ae, and values of ae = 0:02; 0:25; 0:5; 0:75 were tested. Recall that ae = 0:02 is the lower
bound on correlation that we determined is necessary to insure that the FSP with CRN is
at least as efficient as the FSP without CRN.
Thus, we had a total of six configurations: SC with equal variances, MDM with equal
ances, MDM with increasing variances, MDM with decreasing variances, SC with increasing
variances and SC with decreasing variances. For each configuration, 500 macroreplications
(complete repetitions) of the entire experiment were performed. In all experiments, the nominal
probability of correct selection was set at To compare the performance of
the procedures we recorded the total number of basic (unbatched) observations required by
each procedure, and the total number stages (when data are normally distributed all of the
procedures achieve the nominal probability of a correct selection).
4.2 Summary of Results
The experiments showed that the FSP is superior to the other procedures across all of the
configurations we examined. Under difficult configurations, such as the SC with increasing
variances, the FSP's superiority relative to RP and 2SP was more noticeable as the number
of systems increased.
As we saw in the Figure 3, the expected maximum number of basic observations that
the FSP might take from system i, E[bN i ], increases as batch size increases (number of
batches decreases); this was born out in the experiments as the total actual number of
observations taken also increased as batch size b increased. However, the total number of
basic observations increased more slowly for the FSP than for RP or 2SP as batch size
increased. The number of stages behaved as anticipated from our analysis of the expected
maximum number of stages: first decreasing, then increasing as the number of batches
increases.
Finally, and not unexpectedly, in the MDM configuration wider spacing between the true
means made both 2SP and FSP work better (eliminate more systems earlier) than they did
otherwise.
4.3 Some Specific Results
Instead of presenting comprehensive results from such a large simulation study, we present
selected results that emphasize the key conclusions.
4.3.1 Effect of Number of Systems
In our experiments the FSP outperformed all of the other procedures under every config-
uration; see Table 2 and Table 3 for an illustration. Reductions of more than 50% in the
number of basic observations, as compared to RP and 2SP, were obtained in most cases. As

Table

2: Total number of basic (unbatched) observations when the number of systems is
and the spacing between the means is as a function of batch size b and
induced correlation (ae).
MDM MDM SC SC
Procedure increasing var decreasing var increasing var decreasing var

Table

3: Total number of basic (unbatched) observations when the number of systems is
and the spacing between the means is as a function of batch size b and
induced correlation (ae).
MDM MDM SC SC
Procedure increasing var decreasing var increasing var decreasing var
the number of systems increased under difficult configurations-such as MDM with increasing
variances or SC with increasing variances-the benefit of the FSP relative to RP and
2SP is even greater.
4.3.2 Effect of Batch Size
Results in Section 3.3 suggest that the total number of basic observations should be an
increasing function of the batch size b (a decreasing function of the number of batches n raw
while the number of stages should decrease, then increase in b. Tables 2-3 show empirical
results for the total number of basic observations, while Table 4 shows the total number of
stages, for different values of b. As expected, the total number of basic observations for the
FSP (as well as for RP and 2SP) is always increasing in b, with the incremental increase
becoming larger as b increases. On the other hand, the number of stages is usually minimized
at shown in Table 4. The number of stages is always 1 or 2 for RP and 2SP.
The total number of basic observations taken by RP and 2SP is more sensitive to the
batch size than FSP is; see Table 3, for example. Under MDM with increasing variances,
the total number of basic observations taken by 2SP when more than four times
larger than when 1. However, for the FSP the number of basic observations was only
about 1.5 times larger when moving from 3. This effect becomes even more
pronounced as number of systems becomes larger.
4.3.3 Effect of Correlation
Results in Section 3.2 suggest that positive correlation larger than 0:02 is sufficient for the
FSP with CRN to outperform the FSP assuming independence. As shown in the empirical
results in Table 5, FSP under independence is essentially equivalent to the FSP under CRN
in terms of the number of basic observations. Of course, a larger positive
correlation makes the FSP even more efficient, and this holds across all of the configurations

Table

4: Total number of stages when number of systems is spacing of the means
is as a function of batch size b and induced correlation (ae).
MDM MDM SC SC
Procedure increasing var decreasing var increasing var decreasing var
26 28 475 342 350 51 43 45

Table

5: Total number of basic (unbatched) observations for the FSP when the number of
systems is spacing of the means is and the batch size is
of correlation ae.
MDM MDM SC SC
ae increasing var decreasing var increasing var decreasing var

Table

Total number of basic (unbatched) observations for the FSP when the number of
systems is the batch size is and the systems are simulated independently as a
function of the spacing of the means ffi=- .
MDM MDM SC SC
ffi=- increasing var decreasing var increasing var decreasing var
that were used in our experiments.
4.3.4 Effect of Spacing
In our experiments spacing between means was defined by multiples of ffi=- , so that small
- implies large spacing. Larger spacing makes it easier for any procedure that screens or
eliminates systems to remove inferior systems. Table 6 shows that, in most cases, the total
number of basic observations for the FSP decreases as - =ffi increases. The exception is the
SC with increasing variances where the FSP actually does worse with wider spacing of the
means (this happened for all values of k and b, and for 2SP as well as FSP). A similar pattern
emerged for the total number of stages.
To explain the counterintuitive results for the SC with increasing variances, recall that
in this configuration all inferior systems have the same true mean, but the variances are
assigned as in the MDM configuration with increasing variances; that is, the variance of the
ith system is oe 2
would be in the MDM configuration. Therefore,
larger ffi=- implies larger spacing, and larger spacing implies variances that increase much
faster. Thus, in this example the effect of increasing the variances of the inferior systems is
greater than the effect of spacing the means farther apart. This is consistent with what we
have seen in other studies: inferior systems with large variances provide difficult cases for
elimination procedures.
Conclusions
In this paper we presented a fully sequential, indifference-zone selection procedure that allows
for unequal variances, batching and common random numbers. As we discussed in Section 4,
the procedure is uniformly superior to two existing procedures across all the scenarios we
examined, and it is significantly more efficient when the number of systems is large or the
correlation induced via CRN is large. One advantage of the FSP is that it is easy to account
for the effect of CRN, which is not true of 2SP, for instance (see Nelson, Swann, Goldsman
and Song 1998 for a discussion of this point).
The results in this paper suggest several possibilities for improving the FSP. One is to
search for a tighter continuation region than the triangular one suggested by Fabian's lemma.
A tighter region would seem to be possible since our estimates of the true probability of
correct selection for the FSP (not reported here) show that it is typically greater than the
nominal
Although we did consider the effect of batching, our results are most relevant for the
situation in which we batch to reduce the number of stages or to improve the approximation
of normality, rather than to mitigate the dependence in a single replication of a steady-state
simulation. The effect of such dependence on the performance of the FSP should be
investigated before we would recommend routine use in steady-state simulation experiments
that employ a single replication from each system.



--R

A comparison of the performances of procedures for selecting the normal population having the largest mean when the populations have a common unknown variance.
Design and Analysis for Statistical Selection
Using ranking and selection to clean up after a simulation search.
Note on Anderson's sequential procedures with triangular boundary.

Comparing systems via simulation.
Statistical screening
An improvement on Paulson's sequential ranking procedure.
An improvement on Paulson's procedure for selecting the population with the largest mean from k normal populations with a common unknown variance.
Multiple Comparison Procedures.
Multiple comparisons: Theory and methods.
Asymptotically optimal procedures for sequential adaptive selection of the best of several normal means.
Getting more from the data in a multinomial selection problem.
Efficient multinomial selection in simulation.
Comparing simulated systems based on the probability of being the best.


Comparisons with a standard in simulation experiments.
Simple procedures for selecting the best simulated system when the number of alternatives is large.
A sequential procedure for selecting the population with the largest mean from k normal populations.

Communications in Statistics
Statistical methods related to the law of the iterated logarithm.
Sequential procedures with elimination for selecting the best of k normal populations.
Multiple comparisons in model I one-way anova with unequal variances
--TR
Multiple comparison procedures
Getting more from the data in a multinomial selection problem
Statistical screening, selection, and multiple comparison procedures in computer simulation
Two-stage multiple-comparison procedures for steady-state simulations
Evaluating the probability of a good selection
New Two-Stage and Sequential Procedures for Selecting the Best Simulated System
Simple Procedures for Selecting the Best Simulated System When the Number of Alternatives is Large
Ranking and Selection for Steady-State Simulation
Comparisons with a Standard in Simulation Experiments
New Procedures to Select the Best Simulated System Using Common Random Numbers

--CTR
Harry Ma , Thomas R. Willemain, Better selection of the best, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
Takayuki Osogami, Finding probably best system configurations quickly, ACM SIGMETRICS Performance Evaluation Review, v.34 n.3, December 2006
Jamie R. Wieland , Barry L. Nelson, An odds-ratio indifference-zone selection procedure for Bernoulli populations, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
Hua Shen , Hong Wan, Controlled sequential factorial design for simulation factor screening, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Roy R. Creasey, Jr. , K. Preston White, Jr., Comparison of limit standards using a sequential probability ratio test, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
Takayuki Osogami , Toshinari Itoko, Finding probably better system configurations quickly, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
Takayuki Osogami , Sei Kato, Optimizing system configurations quickly by guessing at the performance, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
Kirk C. Benson , David Goldsman , Amy R. Pritchett, Ranking and selection procedures for simulation, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
L. Jeff Hong , Barry L. Nelson, Indifference zone selection procedures: an indifference-zone selection procedure with minimum switching and sequential sampling, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
Juta Pichitlamken , Barry L. Nelson, Comparing systems via stochastic simulation: selection-of-the-best procedures for optimization via simulation, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
Kirk C. Benson , David Goldsman , Amy R. Pritchett, Applying statistical control techniques to air traffic simulations, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
Seong-Hee Kim, Efficient simulation procedures: comparison with a standard via fully sequential procedures, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
Todd A. Sriver , James W. Chrissis, Combined pattern search and ranking and selection for simulation optimization, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
E. Jack Chen , W. David Kelton, Indifference zone selection procedures: inferences from indifference-zone selection procedures, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
David Goldsman , William S. Marshall , Seong-Hee Kim , Barry L. Nelson, Ranking and selection for steady-state simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
Sigrn Andradttir , David Goldsman , Lee W. Schruben , Bruce W. Schmeiser , Enver Ycesan, Analysis methodology: are we done?, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Seong-Hee Kim, Comparison with a standard via fully sequential procedures, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.2, p.155-174, April 2005
Gwendolyn J. Malone , Seong-Hee Kim , David Goldsman , Demet Batur, Performance of variance updating ranking and selection procedures, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Susan M. Sanchez , R. Kevin Wood, The "BEST" algorithm for solving stochastic mixed integer programs, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
Michael C. Fu , Jian-Qiang Hu , Chun-Hung Chen , Xiaoping Xiong, Simulation Allocation for Determining the Best Design in the Presence of Correlated Sampling, INFORMS Journal on Computing, v.19 n.1, p.101-111, January 2007
David Goldsman , Seong-Hee Kim , Barry L. Nelson, Statistical selection of the best system, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Jrgen Branke , Stephen E. Chick , Christian Schmidt, New developments in ranking and selection: an empirical comparison of the three main approaches, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Mahmoud H. Alrefaei , Ameen J. Alawneh, Selecting the best stochastic system for large scale problems in DEDS, Mathematics and Computers in Simulation, v.64 n.2, p.237-245, 27 January
Stephen E. Chick , Noah Gans, Simulation selection problems: overview of an economic analysis, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
Douglas J. Morrice , John C. Butler, Ranking and selection with multiple "targets", Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
Sigrn Andradttir , David Goldsman , Seong-Hee Kim, Finding the best in the presence of a stochastic constraint, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Mary Court , Jennifer Pittman , Christos Alexopoulos , David Goldsman , Seong-Hee Kim , Margaret Loper , Amy Pritchett , Jorge Haddock, A framework for simulating human cognitive behavior and movement when predicting impacts of catastrophic events, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
David Goldsman , Barry L. Nelson, Statistical selection of the best system, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
Sigrn Andradttir, Simulation optimization with countably infinite feasible regions: Efficiency and convergence, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.4, p.357-374, October 2006
Seong-Hee Kim , Barry L. Nelson, Selecting the best system: selecting the best system: theory and methods, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
Christos Alexopoulos , Seong-Hee Kim, Review of advanced methods for simulation output analysis, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
Christos Alexopoulos , Seong-Hee Kim, Statistical analysis of simulation output: output data analysis for simulations, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
James R. Swisher , Sheldon H. Jacobson , Enver Ycesan, Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures: A survey, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.2, p.134-154, April
variance reduction;multiple comparisons;ranking and selection;output analysis