Performance of variance updating ranking and selection procedures

ABSTRACT

Kim and Nelson (2005) developed two indifference-zone procedures for steady-state simulation where the goal is to find the system with the largest or smallest expected steady-state performance measure. One of the procedures, called KN++, updates a variance estimate as more observations become available and is proven to be asymptotically valid when there is no dependence across systems (for example, there is no use of common random numbers). Their procedure exhibits significant improvement over other existing procedures for use in steady-state simulation. In this paper, we first present a modification of KN++ that is asymptotically valid with the use of common random numbers. Then, we study how well KN++ works when data within a system are independent and identically distributed, but data between systems may be positively correlated. Specific applications include the finding-the-best problem when (i) the data are normal, and (ii) the data are Bernoulli.

REFERENCES

• 1: Bechhofer, R. E., J. Kiefer, and M. Sobel. 1968. Sequential Identification and Ranking Procedures (with Special Reference to Koopman-Darmois Populations). Chicago: University of Chicago Press.
• 2: Bechhofer, R. E. and R. V. Kulkarni. 1982. Closed adaptive sequential procedures for selecting the best of k 2 Bernoulli populations. In Statistical Decision Theory and Related Topics, III, eds. S. S. Gupta and J. O. Berger, Vol. 1, 61--108, New York: Academic Press.
• 3: Billingsley, P. 1968. Convergence of Probability Measures. New York: John Wiley & Sons.
• 4: Justin Boesel , Barry L. Nelson , Seong-Hee Kim, Using Ranking and Selection to "Clean Up" after Simulation Optimization, Operations Research, v.51 n.5, p.814-825, September 2003 [doi>10.1287/opre.51.5.814.16751]
• 5: Cario, M. C. and B. L. Nelson. 1997. Modeling and generating random vectors with arbitrary marginal distributions and correlation matrix. Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois.
• 6: Chiahon Chien , David Goldsman , Benjamin Melamed, Large-sample results for batch means, Management Science, v.43 n.9, p.1288-1295, Sept. 1997 [doi>10.1287/mnsc.43.9.1288]
• 7: Halim Damerdji, Strong consistency of the variance estimator in steady-state simulation output analysis, Mathematics of Operations Research, v.19 n.2, p.494-512, May 1994 [doi>10.1287/moor.19.2.494]
• 8: Damerdji, H. 1995. Mean-square consistency of the variance estimator in steady-state simulation output analysis. Operations Research, 43:282--291.
• 9: Damerdji, H. and D. Goldsman. 1995. Consistency of several variants of the standardized time series area variance estimator. Naval Research Logistics, 42:1161--1176.
• 10: Halim Damerdji , Shane G. Henderson , Peter W. Glynn, Computational efficiency evaluation in output analysis, Proceedings of the 29th conference on Winter simulation, p.208-215, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268481]
• 11: Goldsman, D. and B. L. Nelson. 1998. Comparing systems via simulation. In Handbook of Simulation: Principles, Methodology, Advances, Applications, and Practice, ed. J. Banks, 273--306. New York: John Wiley & Sons.
• 12: Seong-Hee Kim , Barry L. Nelson, A fully sequential procedure for indifference-zone selection in simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.3, p.251-273, July 2001 [doi>10.1145/502109.502111]
• 13: Kim, S.-H. and B. L. Nelson. 2005. On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Accepted for publication in Operations Research.
• 14: Malone, G. 2005. Ranking and Selection Procedures for Bernoulli and Multinomial Data. Doctoral Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia.
• 15: Barry L. Nelson , Julie Swann , David Goldsman , Wheyming Song, Simple Procedures for Selecting the Best Simulated System When the Number of Alternatives is Large, Operations Research, v.49 n.6, p.950-963, November 2001 [doi>10.1287/opre.49.6.950.10019]
• 16: Paulson, E. 1993. Sequential procedures for selecting the best one of k Koopman-Darmois populations. Unpublished.
• 17: Sobel, M. and M. J. Huyett. 1957. Selecting the best one of several binomial populations. Bell System Technical Journal, 36:537--576.