Correlation-induction techniques for estimating quantiles in simulation experiments

ABSTRACT

To estimate selected quantiles of the response of a finite-horizon simulation, we develop statistical methods based on correlation-induction techniques for variance reduction, with emphasis on antithetic variates and Latin hypercube sampling. The proposed multiple-sample quantile estimator is the average of negatively correlated quantile estimators computed from disjoint samples of the response, where negative correlation is induced between corresponding responses in different samples while mutual independence of responses is maintained within each sample. The proposed single-sample quantile estimator is computed from negatively correlated responses within one overall sample. We establish a central limit theorem for the single-sample estimator based on Latin hypercube sampling, showing that asymptotically this estimator is unbiased and has smaller variance than the comparable direct-simulation estimator based on independent replications. We also show that if the response is monotone in the simulation's random-number inputs and if the response satisfies some other regularity conditions, then asymptotically the multiple-sample estimator is unbiased and has smaller mean square error than the direct-simulation estimator.

REFERENCES

• 1: Athanassios N. Avramidis, Variance reduction for quantile estimation via correlation induction, Proceedings of the 24th conference on Winter simulation, p.572-576, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167639]
• 2: Avramidis, A. N. 1993. Variance reduction techniques for simulation with applications to stochastic networks. Ph.D. dissertation, School of Industrial Engineering, Purdue University, West Lafayette, Indiana.
• 3: Avramidis, A. N., K. W. Bauer, Jr., and J. R. Wilson. 1991. Simulation of stochastic activity networks using path control variates. Naval Research Logistics 38 (2): 183-201.
• 4: Avramidis, A. N., and J. R. Wilson. 1995a. Integrated variance reduction strategies for simulation. Operations Research (to appear).
• 5: Avramidis, A. N., and J. R. Wilson. 1995b. Correlation-induction techniques for estimating quantiles in simulation experiments. Technical Report 95-05, Department of Industrial Engineering, North Carolina State University, Raleigh, North Carolina.
• 6: Billingsley, P. 1986. Probability and measure. 2d ed. New York: John Wiley & Sons.
• 7: Labs Bell , John M. Chambers , Peter J. Bickel , William S. Cleveland , Richard M. Dudley, S an Interactive Environment for Data Analysis and Graphics, CRC Press, Inc., Boca Raton, FL, 1984
• 8: David, H. A. 1981. Order statistzcs. 2d ed. New York: John Wiley & Sons.
• 9: J. C. Hsu , B. L. Nelson, Control variates for quantile estimation, Management Science, v.36 n.7, p.835-851, Jul. 1990 [doi>10.1287/mnsc.36.7.835]
• 10: Lehmann, E. L. 1966. Some concepts of dependence. Annals of Mathematical Statistics 37:1137-1153.
• 11: P. A. W. Lewis , R. L. Ressler, Variance reduction of quantile estimates via nonlinear control, Proceedings of the 21st conference on Winter simulation, p.450-454, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76795]
• 12: McKay, M. D., l~. J. Beckman, and W. J. Conover. 1979. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Tech~ometrics 21 (2): 239- 245.
• 13: Barry L. Nelson , D. Richards, Control variate remedies, Operations Research, v.38 n.6, p.974-992, Nov./Dec. 1990 [doi>10.1287/opre.38.6.974]
• 14: Owen, A. B. 1992a. A central limit theorem for Latin hypercube sampling. Journal of the Royal Statistical Society. Series B 54 (2): 541-551.
• 15: Owen, A. B. 1992b. Orthogonal arrays for computer integration and visualization. Statzstzca S~nzca 2:2.
• 16: Schafer, R.E. 1974. On assessing the precision of simulations. Journal of Statzstical Computation and Simulation 3:67-69.
• 17: Schmeiser, B. W. 1990. Simulation experiments. Chap. 7 in Handbooks in OR ~ MS, Volume 2, ed. D. P. Heyman and M. J. Sobel, 295-330. Amsterdam: North-Holland.
• 18: Serfling, R.J. 1980. Approzzmation theorems of mathematical statzstics. New York: John Wiley & Sons.
• 19: Michael Stein, Large sample properties of simulations using latin hypercube sampling, Technometrics, v.29 n.2, p.143-151, May 1, 1987 [doi>10.2307/1269769]
• 20: Wilson, J. R., D. K. Vaughan, E. Naylor and R. G. Voss. 1982. Analysis of Space Shuttle ground operations. Simulation 38 (6): 187-203.
• 21: Zelterman, D. 1987. Estimating percentage points by simulation. Journal of Cotatist~cal Computation and Cozmulation 27:107-125.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Mathematical induction

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Theory