Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T12:32:15.026Z Has data issue: false hasContentIssue false

Comparing stochastic systems using regenerative simulation with common random numbers

Published online by Cambridge University Press:  01 July 2016

Philip Heidelberger*
Affiliation:
IBM Thomas J. Watson Research Center
Donald L. Iglehart*
Affiliation:
Stanford University
*
Postal address: IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, N.Y. 10598, U.S.A.
∗∗Postal address: Department of Operations Research, Stanford University, Stanford, CA 94305, U.S.A.

Abstract

Suppose two alternative designs for a stochastic system are to be compared. These two systems can be simulated independently or dependently. This paper presents a method for comparing two regenerative stochastic processes in a dependent fashion using common random numbers. A set of sufficient conditions is given that guarantees that the dependent simulations will produce a variance reduction over independent simulations. Numerical examples for a variety of simple stochastic models are included which illustrate the variance reduction achieved.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1979 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported by NSF Grant MCS-23607 and ONR Contract N00014-76-C-0578.

References

Andreasson, I. J. (1972) Antithetic methods in queueing simulations. Report NA 72.58, Department of Computer Science, The Royal Institute of Technology, Stockholm, Sweden.Google Scholar
Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
Chung, K. L. (1960) Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin.Google Scholar
Crane, M. A. and Lemoine, A. J. (1977) An Introduction to the Regenerative Method for Simulation Analysis. Springer-Verlag, Berlin.CrossRefGoogle Scholar
Daley, D. J. (1968) Stochastically monotone Markov chains. Z. Wahrscheinlichkeitsth. 10, 305317.CrossRefGoogle Scholar
Esary, J. D., Proschan, F. and Walkup, D. W. (1967) Association of random variables with applications. Ann. Math. Statist. 38, 14661474.CrossRefGoogle Scholar
Fishman, G. S. (1973) Concepts and Methods in Discrete Event Digital Simulation. Wiley, New York.Google Scholar
Hordijk, A., Iglehart, D. L. and Schassberger, R. (1976) Discrete time methods for simulating continuous time Markov chains. Adv. Appl. Prob. 8, 772778.Google Scholar
Iglehart, D. L. (1978) The regenerative method for simulation analysis. In Current Trends in Programming Methodology, III. Software Modeling, ed. Chandy, K. M. and Yeh, R. T., Chapter 2, 5271, Prentice–Hall, Englewood Cliffs, N.J. Google Scholar
Iglehart, D. L. and Lemoine, A. J. (1974) Approximations for the repairman problem with two repair facilities, II: spares. Adv. Appl. Prob. 6, 147158.Google Scholar
Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process with applications to random walk. Ann. Math. Statist. 27, 147161.Google Scholar
Kleijnen, J. P. C. (1974) Statistical Techniques in Simulation, Part I. Dekker, New York.Google Scholar
Learmonth, G. P. and Lewis, P. A. W. (1973) Naval Postgraduate School random number generator package llrandom. Naval Postgraduate School Report NP555LW73061A, Monterey, Calif.Google Scholar
Mitchell, B. (1973) Variance reduction by antithetic variates in GI/G/1 queueing simulations. Opns. Res. 21, 988997.CrossRefGoogle Scholar
Smith, W. L. (1955) Regenerative stochastic processes. Proc. R. Soc. London A 232, 631.Google Scholar