Abstract
The regenerative method possesses certain asymptotic properties that dominate those of other steady-state simulation output analysis methods, such as batch means. Therefore, applying the regenerative method to steady-state discrete-event system simulations is of great interest. In this paper, we survey the state of the art in this area. The main difficulty in applying the regenerative method in our context is perhaps in identifying regenerative cycle boundaries. We examine this issue through the use of the "smoothness index." Regenerative cycles are easily identified in systems with unit smoothness index, but this is typically not the case for systems with nonunit smoothness index. We show that "most" (in a certain precise sense) discrete-event simulations will have nonunit smoothness index, and extend the asymptotic theory of regenerative simulation estimators to this context.
- Andradóttir, S., Calvin, J. M., and Glynn, P. W. 1995. Accelerated regeneration for Markov chain simulations. Probability in the Engineering and Informational Sciences 9, 497--523.Google Scholar
- Asmussen, S. 1987. Applied Probability and Queues. Wiley, Chichester.Google Scholar
- Billingsley, P. 1968. Convergence of Probability Measures. Wiley, New York.Google Scholar
- Billingsley, P. 1986. Probability and Measure (2nd ed.). Wiley, New York.Google Scholar
- Bratley, P., Fox, B. L., and Schrage, E. L. 1987. A Guide to Simulation (2nd ed.). Springer-Verlag, New York. Google Scholar
- Burman, D. 1981. Insensitivity in queueing systems. Advances in Applied Probability 13, 846--859.Google Scholar
- Chow, Y. S., Robbins, H., and Teicher, H. 1965. Moments of randomly stopped sums. Ann. Math. Stat. 36, 789--799.Google Scholar
- Fossett, L. D. 1979. Simulating generalized semi-Markov processes. Tech. rep., Dept. of Operations Research, Stanford University, Stanford CA.Google Scholar
- Glynn, P. W. 1982. Simulation Output Analysis for General State Space Markov Chains. Ph.D. dissertation, Dept. of Operations Research, Stanford University, Stanford, CA.Google Scholar
- Glynn, P. W. 1989a. The covariance function of a regenerative process. Tech. rep., Department of Operations Research, Stanford University, Stanford CA.Google Scholar
- Glynn, P. W. 1989b. A GSMP formalism for discrete event systems. Proc. IEEE 77, 14--23.Google Scholar
- Glynn, P. W. 1994. Some topics in regenerative steady-state simulation. Acta Applic. Mathem. 34, 225--236.Google Scholar
- Glynn, P. W. and Heidelberger, P. 1990. Bias properties of budget constrained simulations. Oper. Res. 38, 801--814. Google Scholar
- Glynn, P. W. and Iglehart, D. L. 1987. A joint central limit theorem for the sample mean and the regenerative variance estimator. Ann. Oper. Res. 8, 41--55.Google Scholar
- Glynn, P. W. and Iglehart, D. L. 1993. Conditions for the applicability of the regenerative method. Manage. Sci. 39, 1108--1111. Google Scholar
- Glynn, P. W. and L'Ecuyer, P. 1995. Likelihood ratio gradient estimation for stochastic recursions. Advances Appl. Prob. 27, 1019--1053. Google Scholar
- Goldsman, D. and Meketon, M. S. 1986. A comparison of several variance estimators. Tech. rep., School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta GA.Google Scholar
- Grenander, U. and Rosenblatt, M. 1984. Statistical Analysis of Stationary Time Series (2nd ed.). Chelsea, New York NY.Google Scholar
- Haas, P. J. 1985. Recurrence and Regeneration in Non-Markovian Simulations. Ph.D. dissertation, Dept. of Operations Research, Stanford University, Stanford, CA.Google Scholar
- Haas, P. J. 1999. On simulation output analysis for generalized semi-Markov processes. Commun. Stat.: Stoch. Models 15, 53--80.Google Scholar
- Haas, P. J. and Shedler, G. S. 1987. Regenerative generalized semi-Markov processes. Commun. Stat.: Stoch. Models 3, 409--438.Google Scholar
- Henderson, S. G. and Glynn, P. W. 1999a. Can the regenerative method be applied to discrete-event simulation? In P. A. Farrington, H. Black Nembhard, D. T. Sturrock, and G. W. Evans, Eds., Proceedings of the 1999 Winter Simulation Conference (Piscataway NJ, 1999), pp. 367--373. IEEE. Google Scholar
- Henderson, S. G. and Glynn, P. W. 1999b. Derandomizing variance estimators. Oper. Res. 47, 907--916. Google Scholar
- Iglehart, D. L. 1975. Simulating stable stochastic systems, V: comparison of ratio estimators. Naval Res. Log. Quart. 22, 553--565.Google Scholar
- Janson, S. 1983. Renewal theory for m-dependent variables. Ann. Prob. 11, 558--568.Google Scholar
- König, D., Matthes, K., and Nawrotzki, K. 1967. Verallgemeinerungen der Erlangschen und Engsetschen Formeln. Akadamie-Verlag, Berlin.Google Scholar
- Law, A. M. and Kelton, W. D. 2000. Simulation Modeling and Analysis (3rd ed.). McGraw-Hill, New York. Google Scholar
- Meketon, M. S. and Heidelberger, P. 1982. A renewal theoretic approach to bias reduction in regenerative simulations. Manage. Sci. 28, 173--181.Google Scholar
- Meyn, S. P. and Tweedie, R. L. 1993. Markov Chains and Stochastic Stability. Springer-Verlag, London.Google Scholar
- Nummelin, E. 1984. General Irreducible Markov Chains and Non-Negative Operators. Cambridge University Press.Google Scholar
- Shedler, G. S. 1987. Regeneration and Networks of Queues. Springer-Verlag, New York. Google Scholar
- Shedler, G. S. 1993. Regenerative Stochastic Simulation. Academic Press, Boston.Google Scholar
- Song, W. T. and Schmeiser, B. W. 1995. Optimal mean-squared-error batch sizes. Manage. Sci. 41, 110--123. Google Scholar
- Whitt, W. 1980. Continuity of generalized semi-Markov processes. Math. Oper. Res. 5, 494--501.Google Scholar
- Wolff, R. W. 1989. Stochastic Modeling and the Theory of Queues. Prentice Hall, Englewood Cliffs NJ.Google Scholar
Index Terms
Regenerative steady-state simulation of discrete-event systems
Recommendations
Estimation of steady-state central moments by the regenerative method of simulation
Let X be a possible recurrent regenerative process on state space S with steady-state distribution @p. Given a function @?: S -> R, we consider the problem of estimating the steady-state central moments @m"k(@?) = @?"s(@?(x)-r)^k@p(dx) where r is the ...
Steady-state analysis of a discrete-time batch arrival queue with working vacations
This paper analyzes a discrete-time batch arrival queue with working vacations. In a Geo^X/G/1 system, the server works at a lower speed during the vacation period which becomes a lower speed operation period. This model is more appropriate for the ...
How Hard are Steady-State Queueing Simulations?
Special Issue on Don IglehartSome queueing systems require tremendously long simulation runlengths to obtain accurate estimators of certain steady-state performance measures when the servers are heavily utilized. However, this is not uniformly the case. We analyze a number of ...
Comments