# A New Approach to Estimate the Critical Constant of Selection Procedures

Authors: E. Jack Chen; Min Li
Journal: Advances in Decision Sciences
 (2010)

---

## Abstract

A solution to the ranking and selection problem of determining a subset of sizem containing at least c of the v best from k normal distributions has been developed. The best distributions are those having, for example, (i) the smallest
means, or (ii) the smallest variances. This paper reviews various applicable algorithms and supplies the operating constants needed
to apply these solutions. The constants are computed using a histogram approximation algorithm and Monte Carlo integration.


---

## Body

## 1. Introduction

Discrete-event simulation has been widely  used to compare alternative system designs or operating policies. When evaluatingk alternative system designs, we select one or more systems as the best and control the probability that the selected systems really are the best. This goal is achieved by using a class of ranking and selection (R&S) procedures in simulation (see [1] for a detailed description). Chen [2, 3] considered a general version of this problem to select a subset of size m containing at least c of the v best of k normally distributed systems with the lth smallest θil (mean or variance), where θi1≤θi2≤⋯≤θik represent proposed sampling solutions. Moreover, in practice, if the difference between θiv and θiv+1 is very small, we might not care if we mistakenly choose system iv+1, whose expected response is θiv+1. The “practically significant” difference d* (a positive real number) between a desired and a satisfactory system is called the indifference zone in the statistical literature, and it represents the smallest difference about which we care.If the absolute difference isθiv+1-θiv<d* or the relative difference is θiv+1/θiv<d*, we say that the systems are in the indifference zone for correct selection. Note that the absolute difference and the relative difference are two completely separate problems. On the other hand, if the absolute difference is θiv+1-θiv≥d* or the relative difference is θiv+1/θiv≥d*, we say that the systems are in the preference zone for correct selection.LetP* denote the required minimal probability of correct selection. The goal is to make a correct selection (CS) with probability at least P*, where(1.1)P*≥P(c,v,m,k)=(km)-1∑i=cmin(m,v)(vi)(k-vm-i).
If P*<P(c,v,m,k), the precision requirement is satisfied by choosing the subset at random. The minimal correct selection probability P* and the “indifference” amount d* are specified by the user. If c=v=m=1, the problem is to choose the best system. When m>c=v=1, we are interested in choosing a subset of size m that contains the best. If c=v=m>1, we are interested in choosing the m best systems.This paper proposes a new approach to estimate the operating constants needed to apply the solutions in [2, 3]. We first review these procedures in Sections 2 and 3. We then describe the histogram approximation algorithm of Chen and Kelton [4] and the Monte Carlo integration technique used to compute tables of operating constants in Section 4. A brief illustration demonstrating how to apply the tables is provided in Section 5.


## 2. Selection Problems with Respect to Means

Considerk independent normal distributions having means μi and variances σi2, i=1,2,…,k. It is assumed that μi and σi2 are unknown. Selection procedures generally sample certain observations from each alternative (at the initial stage) and select the systems having the best sample means as the best systems. The question that arises is whether enough observations have been sampled and if not, the number of additional observations that are needed. Hence, at the second stage of the procedure, the required number of observations is generally estimated based on the available sample variances and sample means.Extending the work of Dudewicz and Dalal [5] and Mahamunulu [6], Chen [3] proposed a two-stage solution when the parameter of interest θi is μi. Chen's procedure is as follows. Let Xij, i=1,2,…,k; j=1,2,…,ni be the jth observation from the ith population. Randomly sample n0 observations from each of the k populations. Let X̅i(1)=(Σj=1n0Xij)/n0 be the usual unbiased estimate of μi and let si2(n0)=Σj=1n0(Xij-X̅i(1))/(n0-1) be the usual unbiased estimate of σi2. Compute(2.1)ni=max(n0+1,⌈(hsi(n0)d*)2⌉),fori=1,2,…,k,
where h is a constant to be described later and ⌈z⌉ denotes the integer ceiling (round-up) of the real number z. Randomly sample an additional (ni-n0) observations from the ith population.We then compute the second-stage sample means:(2.2)X̅i(2)=1ni-n0∑j=n0+1niXij,fori=1,2,…,k.
Define the weights(2.3)Wi1=n0ni[1+1-nin0(1-(ni-n0)(d*)2h2si2(n0))]
and Wi2=1-Wi1, for i=1,2,…,k. Compute the weighted sample means(2.4)X̃i=Wi1X̅i(1)+Wi2X̅i(2),fori=1,2,…,k
and select the m systems with the smallest X̃i values. Note that the expression for Wi1 was chosen to guarantee that (X̃i-μi)/(d*/h) has a t distribution with (n0-1) degrees of freedom (d.f., see [5]).The derivation is based on the fact that fori=1,2,…,k,(2.5)Ti=X̃i-μid*/h
has a t distribution with (n0-1) d.f., where h depends on k, m, v, c, n0, and P*. Note that Ti's are independent. Furthermore, correct selection occurs if and only if the cth smallest μil's of systems il for l=1,2,…,v is less than the (m-c+1)th smallest μil's of systems il for l=v+1,v+2,…,k.Letf and F, respectively, denote the probability density function (pdf) and the cumulative distribution function (cdf) of the random variable Y. Hogg and Craig ([7], page 198) show that the pdf of the uth order statistic out of n observations of Y is(2.6)gn,u(y[u])=β(F(y[u]);u,n-u+1)f(y[u]),
where β(x;a,b)=(Γ(a+b)/Γ(a)Γ(b))xa-1(1-x)b-1 is the beta distribution with shape parameters a and b. In our case, f and F are, respectively, the pdf and cdf of the t distribution with (n0-1) d.f. For selection problems with respect to means, the least favorable configuration (LFC) occurs when μi1=μi2=⋯=μiv and μiv+d*=μiv+1=⋯=μik (Mahamunulu [6]). Let X̃[c] be the cth smallest weighted sample mean from X̃il for l=1,2,…,v and μ[c] be its unknown true mean. Let X̃[u] be the uth(u=m-c+1) smallest weighted sample mean from X̃il for l=v+1,v+2,…,k and μ[u] be its unknown true mean. We can write the probability of correct selection as(2.7)P(CS)=P[X̃[c]<X̃[u]]=P[X̃[c]-μ[c]d*/h≤X̃[u]-μ[u]d*/h+μ[u]-μ[c]d*/h]=P[T[c]≤T[u]+μ[u]-μ[c]d*/h]≥P[T[c]≤T[u]+h].
The inequality follows because μ[u]-μ[c]≥μiv+1-μiv≥d*. Furthermore, if da(μ[u],μ[c])=μ[u]-μ[c] is used instead of d* in the above equations, we obtain strict equality.Note thatT[c]~β(F(T[c]);c,v-c+1)f(T[c]) and T[u]~β(F(T[u]);m-c+1,k-v-m+c)f(T[u]). Here “~” denotes “is distributed as.” Hence,(2.8)P(CS)≥∫-∞∞∫-∞y+hβ(F(x);c,v-c+1)f(x)β(F(y);m-c+1,k-v-m+c)f(y)dxdy.
We equate the right-hand side to P* to solve for h. The value of h is determined by P[T[c]≤T[u]+h]=P*. Let τ=T[c]-T[u]. Then P[τ≤h]=P*. That is, under the LFC, the value of h is the P* quantile of the distribution of τ.For example, if we are interested in the probability of correctly selecting a subset of size5 containing 3 of the first 3 best from 10 alternatives, then T[c]~g3,3(t[c]) and T[u]~g7,3(t[u]). Furthermore, if the initial sample size is n0=20, then f and F are, respectively, the pdf and cdf of the t-distribution with 19 d.f.Letw[c][u] denote the one-tailed P* confidence interval (c.i.) half-width of (μ[u]-μ[c]). We conclude that the sample sizes allocated by (2.1) achieve w[c][u]≤d*. That is, the indifference amount d* in (2.1) corresponds to the upper bound of the desired c.i. half-width w[c][u]. Hence, under the LFC μ[c]+d*=μ[u], the sample sizes allocated by (2.1) ensure that(2.9)P(CS)=P[X̃[c]<X̃[u]]=P[X̃[c]-X̃[u]-d*<μ[c]-μ[u]]≥P[X̃[c]-X̃[u]-w[c][u]<μ[c]-μ[u]]=P*.
The last equality follows from the definition of the c.i. Note that if w[c][u]>d*, then P(CS)<P*. It can be shown that(2.10)w[c,u]=h2s[c]2(n0)n[c]+s[u]2(n0)n[u].Koenig and Law [8] provide some h values for the case that c=v=1 or c=v=m. This paper supplies a table of the h values with selected c, v, m, and k; where c, v, and m may be different.


## 3. Selection Problems with Respect to Variances

Extending the work of Bechhofer and Sobel [9] and Mahamunulu [6], Chen [2] proposed a single-stage solution when the parameter of interest θi is σi2. Chen's procedure is as follows. Let ni=n0 for i=1,2,…,k. Thus, we use the notation si2 instead of si2(ni) in the rest of this section. Randomly sample n0 observations from each of the k populations and compute si2=Σj=1n0(Xij-X̅i(1))/(n0-1). Select the m systems with the smallest si2.For selection problems with respect to variances, the LFC occurs whenσi12=σi22=⋯=σiv2 and σiv2d*=σiv+12=⋯=σik2 (Mahamunulu [6]). The derivation is based on the fact that (n0-1)si2/σi2 has a χ2 distribution with (n0-1) d.f. Let s[c]2 be the cth smallest sample variance from sil2 for l=1,2,…,v and σ[c]2 be its unknown true variance. Let s[u]2 be the uth(u=m-c+1) smallest sample variance from sil2 for l=v+1,v+2,…,k and σ[u]2 be its unknown true variance. Then(3.1)P(CS)=P[s[c]2<s[u]2]=P[(n0-1)s[c]2σ[c]2≤(n0-1)s[u]2σ[u]2σ[u]2σ[c]2]=P[X[c]≤X[u]σ[u]2σ[c]2]≥P[X[c]≤X[u]d*].
The third equality follows because X[c]=(n0-1)s[c]2/σ[c]2, X[u]=(n0-1)s[u]2/σ[u]2, and(3.2)1<d*≤σiv+12σiv2≤σ[u]2σ[c]2.
Furthermore, if dr(σ[u]2,σ[c]2)=σ[u]2/σ[c]2 is used instead of d* in the above equation, we obtain strict equality. Note that under the LFC, dr(σ[u]2,σ[c]2)=d*.Letω and Ω, respectively, denote the pdf and cdf of the χ2 distribution with (n0-1) d.f. Then X[c]~β(Ω(X[c]);c,v-c+1)ω(X[c]) and X[u]~β(Ω(X[u]);m-c+1,k-v-m+c)ω(X[u]). Hence,(3.3)P(CS)≥∫0∞∫0yd*β(Ω(x);c,v-c+1)ω(x)β(Ω(y);m-c+1,k-v-m+c)ω(y)dxdy=v!(c-1)!(v-c)!(k-v)!(m-c)!(k-v-m+c-1)!×∫0∞∫0yd*[Ω(x)]c-1[1-Ω(x)]v-cω(x)[Ω(y)]m-c[1-Ω(y)]k-v-m+c-1ω(y)dxdy.
We can compute P(CS) values under the LFC given k, m, v, c, d*, and n0. Bechhofer and Sobel [9] provide some P(CS) for the cases that k≤4. We provide additional P(CS) values for some selected parameters in Section 4.2.Letγ=X[c]/X[u]. There exists some 0≤p≤1 such that P[γ≤d*]=p. Hence, under the LFC, the value of d* is the p quantile of the distribution of the random variable γ. For example, if we are interested in the probability of correctly selecting a subset of size 5 containing all 3 of the first 3 best from 10 alternatives, then X[c]~g3,3(x[c]) and X[u]~g7,3(x[u]), with f and F replaced by ω and Ω, respectively.If users prefer to specify the indifference amountd* in the absolute form, da(θ,θ0)=θ-θ0, instead of the relative form, dr(θ,θ0)=θ/θ0, when the parameter of interest is a scale parameter, we can transform the absolute indifference amount into the relative indifference, dr(θ,θ0)=1+da(θ,θ0)/θ0. Since θ0 is unknown, the estimator θ̂0 needs to be used and dr(θ,θ0)≈1+d*/θ̂0. Moreover, a conservative adjustment can be used. Rank the sample variances such that sb12<sb22<⋯<sbv2<sbv+12<⋯<sbk2. Let yq be the q quantile of the χ2 distribution with (nbv-1) d.f., where 0<q<1. We can conservatively set dr(σiv+12,σiv2)≈1+d*yq/((nbv-1)sbv2(nbv)) (see [2]). Conversely, if users prefer to specify the indifference amount in the relative form instead of the absolute form when the parameter of interest is the location parameter, we can set da(θ,θ0)≈(d*-1)θ̂0.


## 4. Method of Computation

Analytical solutions to multidimensional integration problems in the previous section are difficult to obtain. Below we show our approaches to findh and P(CS).


### 4.1. Computing the Value ofh

Recall that under the LFC the value ofh is the P* quantile of the distribution of τ. Consequently, we can use any quantile-estimation procedures to estimate the P* quantile of the variable τ given k, m, v, c, and n0. In this section, we briefly review quantile estimates and the histogram-approximation procedure of Chen and Kelton [4].LetX1,X2,…,Xn be a sequence of i.i.d. (independent and identically distributed) random variables from a continuous cdf F(x) with pdf f(x). Let xp (0<p<1) denote the 100pth percentile or the p quantile, which has the property that F(xp)=Pr(X≤xp)=p. Thus, xp=inf{x:F(x)≥p}. If Y1,Y2,…,Yn are the order statistics corresponding to the Xi's from n independent observations (i.e., Yi is the ith smallest of X1, X2, …, Xn), then a point estimator for xp based on the order statistics is the sample p quantile:(4.1)x̂p=y⌈np⌉.Chen and Kelton [4] control the precision of quantile estimates by ensuring that the p quantile estimator x̂p satisfies the following:(4.2)P[xp∈x̂p±ϵ]≥1-α1,orequivalentlyP[|F(x̂p)-p|≤ϵ]≥1-α1.
Using this precision requirement (i.e., (4.2)), the required sample size np for a fixed-sample-size procedure of estimating the p quantile of an i.i.d. sequence is the minimum np that satisfies(4.3)np≥z1-α1/22p(1-p)ϵ2,
where z1-α1/2 is the (1-α1/2) quantile of the standard normal distribution, ϵ is the maximum proportional half-width of the c.i., and (1-α1) is the confidence level. For example, if the data are independent and we would like to have 95% confidence that the coverage of the 0.9 quantile estimator has no more than ϵ=0.0005 deviation from the true but unknown quantile, the required sample size is np≥1382976 (=1.96020.9(1-0.9)/0.00052). Consequently, we are 97.5% confident that the quantile estimate will cover at least p-0.0005 (for p≥0.9), with a sample size of 1382976.The histogram-approximation procedure sets up a series of grid points based on a pilot run. New samples are then stored in the corresponding grids according to their observed value. A histogram is created at the end of the procedure when it has processed the required sample size. Thep quantile estimator is obtained by interpolating among grid points. Interested readers can see [4] for the detailed steps of the histogram-approximation procedure.In the appendix, we show how to generate order statistics random variates without storing and sorting the entire sequence. In order to use this algorithm, we need to be able to perform an inverse transformation of the cdf of the random variable. Unfortunately, the inverse transformation of the cdf of thet-distribution and (2.8) are not available. Nevertheless, numerical methods are available to compute the inverse of the cdf of the t-distribution; see [10]. Hence, the variates T[c] and T[u] can be generated efficiently without sorting a series of t-distributed variables.Table1 shows the resulting h values for several chosen k, m, v, c, n0, and P*. Four significant digits are retained. Negative values indicate that P* can be achieved with a sample size of (n0+1) and are set to 0.Table 1
Values ofh for the subset selection procedure.
P*=0.90P*=0.95kmvc152025301520253073111.7151.6931.6801.6722.1662.1322.1122.09973210.7100.7040.7010.6991.0691.0601.0541.05122.4952.4542.4312.4162.9392.8802.8462.82573310.0720.0720.0710.0710.4130.4100.4080.40721.5111.4951.4861.4801.8651.8431.8301.82233.4953.4143.3683.3393.9983.8873.8253.78683111.8531.8301.8171.8082.3052.2682.2472.23483210.8890.8820.8780.8751.2431.2321.2251.22122.6302.5862.5612.5453.0703.0072.9722.94983310.3290.3260.3240.3230.6570.6520.6480.64621.6861.6671.6561.6492.0372.0111.9961.98733.6213.5333.4843.4534.1224.0043.9393.89793111.9681.9431.9291.9202.4172.3802.3582.34493211.0271.0191.0131.0101.3751.3621.3551.35022.7402.6942.6682.6513.1803.1153.0783.05593310.5080.5040.5010.5000.8280.8210.8160.81421.8181.7961.7841.7762.1632.1332.1162.10633.7233.6303.5793.5464.2214.0964.0283.984104111.7401.7191.7071.6992.1812.1462.1262.114104210.7960.7900.7870.7841.1351.1261.1201.11722.3882.3502.3292.3152.8102.7542.7232.703104310.2700.2680.2670.2660.5780.5740.5710.57021.4531.4391.4311.4261.7701.7511.7411.73332.9772.9202.8892.8693.34033.3253.2823.2551044100000.1500.1490.1480.14820.9290.9220.9170.9141.2231.2121.2061.20232.0642.0392.0242.0152.3962.3622.3432.33143.8883.7883.7323.6964.3814.2494.1754.129105111.4531.4341.4231.4171.8941.8621.8441.832105210.4790.4750.4740.4720.8150.8080.8040.80222.0412.0081.9891.9772.4592.4082.3792.3611053100000.2210.2190.2180.21821.0761.0671.0621.0581.3921.3781.3701.36532.5062.4602.4342.4182.9212.8552.8182.794105410000000020.5100.5060.5040.5030.7970.7910.7880.78531.5601.5441.5351.5291.8711.8491.8371.82943.0272.9662.9322.9103.4483.3643.3183.289


### 4.2. Computing the Probability of Correct Selection P(CS)

Monte Carlo integration can be used to approximately evaluate the integrals. Let hypercubeV be the integration volume and hypercube V′⊆V. Monte Carlo integration picks random uniformly distributed points over some simple domain V, which contains V′, checks whether each point is within V′, and estimates the area of V′ as the area of V multiplied by the fraction of points falling within V′. Suppose that we pick randomly distributed points X1,…,Xn in d-dimensional volume V to determine the integral of a function f in this volume:(4.4)∫fdV≈V〈f〉±V〈f2〉-〈f〉2n,
where(4.5)〈f〉≡1n∑i=1ng(Xi),〈f2〉≡1n∑i=1ng2(Xi)
(see Press et al. [11]). Note that V(〈f2〉-〈f〉)/n is a one standard deviation error estimate of the integral and g is a function to be specified depending on the problem at hand.In our caseV is the unit volume and g will be the indicator function of whether a correct selection was made. Let ri be the index of the ith simulation and(4.6)I(ri)={1,correctselectionwasmadeinsimulationri,0,otherwise.
If we perform n independent simulation replications and the observed P(CS) is p̂, then(4.7)〈f〉≡1n∑i=1nI(ri)=,〈f2〉≡1n∑i=1nI2(ri)=p̂.
Let p denote the true P(CS) with given parameters, that is, p=∫fdV. Then(4.8)p≈p̂±p̂-p̂2n.
Note that the number of times that the best design is selected from n simulation runs has a binomial distribution B(n,p), where n≥0 is the number of trials and 0≤p≤1 is the success probability. Furthermore, when n is large, B(n,p) can be approximated by the normal distribution N(np,np(1-p)) with mean np and variance np(1-p) [7]. Consequently,(4.9)P[p≥p̂-p̂-p̂2n]≥0.84.
If the target p=0.9 and n=1000000, then P[p≥p̂-0.0003]≥0.84.We perform simulation experiments to estimate the value of the integrals. Table2 shows the resulting probability of correct selection (with four significant digits) for several chosen k, m, v, c, and n0.Table 2
Values of P(CS) whenn0=20.
d*kmvc1.21.41.61.82.02.273110.62510.77430.87250.93100.96380.981473210.87320.94950.98090.99310.99760.999120.30900.49420.65620.77910.86300.917273310.96500.99000.99710.99920.99970.999920.61100.78720.89240.94770.97550.988530.09330.20090.33360.46930.59100.692483110.56980.72890.83990.91020.95100.974083210.91340.96260.98490.99430.99780.999120.25150.42830.59550.73030.82750.892983310.93760.98040.99410.99830.99950.999820.52210.72010.85010.92430.96300.982230.06560.15580.27730.40960.53460.643093110.52500.68970.81070.89010.93890.966793210.78440.90160.95870.98370.99380.997620.21050.37720.54510.68770.79500.870593310.90880.96930.99030.99700.99910.999720.45180.66100.81020.90070.94980.975230.04910.12450.23470.36220.48760.6012104110.60140.75930.86510.92860.96360.9822104210.84970.94160.97920.99310.99770.999220.30520.50180.67480.80260.88620.9368104310.94810.98600.99650.99910.99970.999920.59440.79200.90510.96000.98390.993730.11800.26120.43180.59370.72530.8221104410.98410.99680.99940.99980.99990.999920.79430.92200.97330.99140.99720.999130.31310.53720.72250.84660.91950.959140.02650.08150.17440.29310.41970.5394105110.70030.83780.91870.96160.98250.9924105210.91820.97390.99250.99790.99940.999820.44010.64690.79890.89340.94640.9740105310.98060.99600.99920.99980.99990.999920.75530.90060.96420.98810.99620.998830.23700.43890.62990.77550.87110.9294105410.99630.99940.99990.99991.00001.000020.91360.97630.99410.99860.99960.999930.53280.75530.88740.95260.98120.992640.09860.23710.41080.57860.71570.8171


## 4.1. Computing the Value ofh

Recall that under the LFC the value ofh is the P* quantile of the distribution of τ. Consequently, we can use any quantile-estimation procedures to estimate the P* quantile of the variable τ given k, m, v, c, and n0. In this section, we briefly review quantile estimates and the histogram-approximation procedure of Chen and Kelton [4].LetX1,X2,…,Xn be a sequence of i.i.d. (independent and identically distributed) random variables from a continuous cdf F(x) with pdf f(x). Let xp (0<p<1) denote the 100pth percentile or the p quantile, which has the property that F(xp)=Pr(X≤xp)=p. Thus, xp=inf{x:F(x)≥p}. If Y1,Y2,…,Yn are the order statistics corresponding to the Xi's from n independent observations (i.e., Yi is the ith smallest of X1, X2, …, Xn), then a point estimator for xp based on the order statistics is the sample p quantile:(4.1)x̂p=y⌈np⌉.Chen and Kelton [4] control the precision of quantile estimates by ensuring that the p quantile estimator x̂p satisfies the following:(4.2)P[xp∈x̂p±ϵ]≥1-α1,orequivalentlyP[|F(x̂p)-p|≤ϵ]≥1-α1.
Using this precision requirement (i.e., (4.2)), the required sample size np for a fixed-sample-size procedure of estimating the p quantile of an i.i.d. sequence is the minimum np that satisfies(4.3)np≥z1-α1/22p(1-p)ϵ2,
where z1-α1/2 is the (1-α1/2) quantile of the standard normal distribution, ϵ is the maximum proportional half-width of the c.i., and (1-α1) is the confidence level. For example, if the data are independent and we would like to have 95% confidence that the coverage of the 0.9 quantile estimator has no more than ϵ=0.0005 deviation from the true but unknown quantile, the required sample size is np≥1382976 (=1.96020.9(1-0.9)/0.00052). Consequently, we are 97.5% confident that the quantile estimate will cover at least p-0.0005 (for p≥0.9), with a sample size of 1382976.The histogram-approximation procedure sets up a series of grid points based on a pilot run. New samples are then stored in the corresponding grids according to their observed value. A histogram is created at the end of the procedure when it has processed the required sample size. Thep quantile estimator is obtained by interpolating among grid points. Interested readers can see [4] for the detailed steps of the histogram-approximation procedure.In the appendix, we show how to generate order statistics random variates without storing and sorting the entire sequence. In order to use this algorithm, we need to be able to perform an inverse transformation of the cdf of the random variable. Unfortunately, the inverse transformation of the cdf of thet-distribution and (2.8) are not available. Nevertheless, numerical methods are available to compute the inverse of the cdf of the t-distribution; see [10]. Hence, the variates T[c] and T[u] can be generated efficiently without sorting a series of t-distributed variables.Table1 shows the resulting h values for several chosen k, m, v, c, n0, and P*. Four significant digits are retained. Negative values indicate that P* can be achieved with a sample size of (n0+1) and are set to 0.Table 1
Values ofh for the subset selection procedure.
P*=0.90P*=0.95kmvc152025301520253073111.7151.6931.6801.6722.1662.1322.1122.09973210.7100.7040.7010.6991.0691.0601.0541.05122.4952.4542.4312.4162.9392.8802.8462.82573310.0720.0720.0710.0710.4130.4100.4080.40721.5111.4951.4861.4801.8651.8431.8301.82233.4953.4143.3683.3393.9983.8873.8253.78683111.8531.8301.8171.8082.3052.2682.2472.23483210.8890.8820.8780.8751.2431.2321.2251.22122.6302.5862.5612.5453.0703.0072.9722.94983310.3290.3260.3240.3230.6570.6520.6480.64621.6861.6671.6561.6492.0372.0111.9961.98733.6213.5333.4843.4534.1224.0043.9393.89793111.9681.9431.9291.9202.4172.3802.3582.34493211.0271.0191.0131.0101.3751.3621.3551.35022.7402.6942.6682.6513.1803.1153.0783.05593310.5080.5040.5010.5000.8280.8210.8160.81421.8181.7961.7841.7762.1632.1332.1162.10633.7233.6303.5793.5464.2214.0964.0283.984104111.7401.7191.7071.6992.1812.1462.1262.114104210.7960.7900.7870.7841.1351.1261.1201.11722.3882.3502.3292.3152.8102.7542.7232.703104310.2700.2680.2670.2660.5780.5740.5710.57021.4531.4391.4311.4261.7701.7511.7411.73332.9772.9202.8892.8693.34033.3253.2823.2551044100000.1500.1490.1480.14820.9290.9220.9170.9141.2231.2121.2061.20232.0642.0392.0242.0152.3962.3622.3432.33143.8883.7883.7323.6964.3814.2494.1754.129105111.4531.4341.4231.4171.8941.8621.8441.832105210.4790.4750.4740.4720.8150.8080.8040.80222.0412.0081.9891.9772.4592.4082.3792.3611053100000.2210.2190.2180.21821.0761.0671.0621.0581.3921.3781.3701.36532.5062.4602.4342.4182.9212.8552.8182.794105410000000020.5100.5060.5040.5030.7970.7910.7880.78531.5601.5441.5351.5291.8711.8491.8371.82943.0272.9662.9322.9103.4483.3643.3183.289


## 4.2. Computing the Probability of Correct Selection P(CS)

Monte Carlo integration can be used to approximately evaluate the integrals. Let hypercubeV be the integration volume and hypercube V′⊆V. Monte Carlo integration picks random uniformly distributed points over some simple domain V, which contains V′, checks whether each point is within V′, and estimates the area of V′ as the area of V multiplied by the fraction of points falling within V′. Suppose that we pick randomly distributed points X1,…,Xn in d-dimensional volume V to determine the integral of a function f in this volume:(4.4)∫fdV≈V〈f〉±V〈f2〉-〈f〉2n,
where(4.5)〈f〉≡1n∑i=1ng(Xi),〈f2〉≡1n∑i=1ng2(Xi)
(see Press et al. [11]). Note that V(〈f2〉-〈f〉)/n is a one standard deviation error estimate of the integral and g is a function to be specified depending on the problem at hand.In our caseV is the unit volume and g will be the indicator function of whether a correct selection was made. Let ri be the index of the ith simulation and(4.6)I(ri)={1,correctselectionwasmadeinsimulationri,0,otherwise.
If we perform n independent simulation replications and the observed P(CS) is p̂, then(4.7)〈f〉≡1n∑i=1nI(ri)=,〈f2〉≡1n∑i=1nI2(ri)=p̂.
Let p denote the true P(CS) with given parameters, that is, p=∫fdV. Then(4.8)p≈p̂±p̂-p̂2n.
Note that the number of times that the best design is selected from n simulation runs has a binomial distribution B(n,p), where n≥0 is the number of trials and 0≤p≤1 is the success probability. Furthermore, when n is large, B(n,p) can be approximated by the normal distribution N(np,np(1-p)) with mean np and variance np(1-p) [7]. Consequently,(4.9)P[p≥p̂-p̂-p̂2n]≥0.84.
If the target p=0.9 and n=1000000, then P[p≥p̂-0.0003]≥0.84.We perform simulation experiments to estimate the value of the integrals. Table2 shows the resulting probability of correct selection (with four significant digits) for several chosen k, m, v, c, and n0.Table 2
Values of P(CS) whenn0=20.
d*kmvc1.21.41.61.82.02.273110.62510.77430.87250.93100.96380.981473210.87320.94950.98090.99310.99760.999120.30900.49420.65620.77910.86300.917273310.96500.99000.99710.99920.99970.999920.61100.78720.89240.94770.97550.988530.09330.20090.33360.46930.59100.692483110.56980.72890.83990.91020.95100.974083210.91340.96260.98490.99430.99780.999120.25150.42830.59550.73030.82750.892983310.93760.98040.99410.99830.99950.999820.52210.72010.85010.92430.96300.982230.06560.15580.27730.40960.53460.643093110.52500.68970.81070.89010.93890.966793210.78440.90160.95870.98370.99380.997620.21050.37720.54510.68770.79500.870593310.90880.96930.99030.99700.99910.999720.45180.66100.81020.90070.94980.975230.04910.12450.23470.36220.48760.6012104110.60140.75930.86510.92860.96360.9822104210.84970.94160.97920.99310.99770.999220.30520.50180.67480.80260.88620.9368104310.94810.98600.99650.99910.99970.999920.59440.79200.90510.96000.98390.993730.11800.26120.43180.59370.72530.8221104410.98410.99680.99940.99980.99990.999920.79430.92200.97330.99140.99720.999130.31310.53720.72250.84660.91950.959140.02650.08150.17440.29310.41970.5394105110.70030.83780.91870.96160.98250.9924105210.91820.97390.99250.99790.99940.999820.44010.64690.79890.89340.94640.9740105310.98060.99600.99920.99980.99990.999920.75530.90060.96420.98810.99620.998830.23700.43890.62990.77550.87110.9294105410.99630.99940.99990.99991.00001.000020.91360.97630.99410.99860.99960.999930.53280.75530.88740.95260.98120.992640.09860.23710.41080.57860.71570.8171


## 5. An Illustration

As a brief illustration of how to use Tables1 and 2, consider 10 systems with θi being the expected performance of the ith system, i=1,2,…,10. It is desired to select 4 systems such that they include at least 2 of the 3 best systems, the systems that have the smallest θi's. Suppose that for each system the performance of n0=20 sampled observations is measured.If the performance measure is the mean, the question that arises is whether enough observations have been sampled and if not, the number of additional observations that are needed. If the required minimum probability of correct selection is to be at leastP*=0.95 when the difference between μi4 and μi3 is 0.5, then from Table 1, h=1.748. Suppose that the sample variance of system 1 is s12(n0)=32. In this case, the required sample size of system 1 is n1=max(20+1,⌈(1.748×3/0.5)2⌉)=110.If the performance measure is the variance, the question that arises is what the probability guarantee with the chosen parameters will be. If the specified indifference amount is 1.4, that is, the ratio betweenσi42 and σi32 is at least 1.4, then from Table 2 the probability guarantee is approximately 0.79.Since the binomial distribution B(n,p) can be approximated by the normal distribution N(np,np(1-p)), the algorithms discussed in the paper can also be applied when the underlying processes have a binomial distribution, provided that users agree that the approximation is acceptable. Furthermore, it is known that order statistics quantile estimates are asymptotically normal [12]. Consequently, the algorithms are also applicable when the parameter of interest is a quantile; see, for example, [13].



---

*Source: 948359-2010-02-07.xml*