Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T09:26:47.704Z Has data issue: false hasContentIssue false
  • English
  • Français

Accelerated Regeneration for Markov Chain Simulations

Published online by Cambridge University Press:  27 July 2009

Sigrún Andradóttir ,
James M. Calvin  and
Peter W. Glynn
Sigrún Andradóttir
Affiliation:
Department of Industrial Engineering, University of Wisconsin-Madison, 1513 University Avenue, Madison, Wisconsin 53706
James M. Calvin
Affiliation:
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia, 30332
Peter W. Glynn
Affiliation:
Department of Operations Research, Stanford University, Stanford, California 94305
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper describes a generalization of the classical regenerative method of simulation output analysis. Instead of blocking a generated sample path on returns to a fixed return state, a more general scheme to randomly decompose the path is used. In some cases, this decomposition scheme results in regeneration times that are a supersequence of the classical regeneration times. This “accelerated” regeneration is advantageous in several simulation contexts. It is shown that when this decomposition scheme accelerates regeneration relative to the classical regenerative method, it also yields a smaller asymptotic variance of the regenerative variance estimator than the classical method. Several other contexts in which increased regeneration frequency is beneficial are also discussed.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 9 , Issue 4 , October 1995 , pp. 497 - 523
Copyright
Copyright © Cambridge University Press 1995

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.)

References

1.Andradóttir, S., Calvin, J.M., & Glynn, P.W. (1994). Increasing the frequency of regeneration for Markov processes. In Tew, J.D., Manivannan, M.S., Sadowski, D.A., & Seila, A.F. (eds.). Proceedings of the 1994 Winter Simulation Conference. New York: Association for Computing Machinery, pp. 320–323.Google Scholar
2.Asmussen, S. & Melamed, B. (1994). Regenerative simulation of TES processes. Acta Applicandae Mathematicae 34: 237–260.CrossRefGoogle Scholar
3.Athreya, K.B. & Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Transactions of the American Mathematical Society 245: 493–501.CrossRefGoogle Scholar
4.Billingsley, P. (1968). Convergence of probability measures. New York: Wiley.Google Scholar
5.Calvin, J.M. (1994). Return-state independent quantities in regenerative simulation. Operations Research 42: 531–542.CrossRefGoogle Scholar
6.Crane, M.A. & Lemoine, A.J. (1977). An introduction to the regenerative method for simulation analysis. Berlin: Springer-Verlag.CrossRefGoogle Scholar
7.Fox, B. & Glynn, P.W. (1986). Discrete-time conversion for simulating semi-Markov processes. Operations Research Letters 5: 191–196.CrossRefGoogle Scholar
8.Glynn, P.W. (1982). Simulation output analysis for general state space Markov chains. Ph.D. dissertation, Department of Operations Research, Stanford University, Stanford, CA.Google Scholar
9.Glynn, P.W. (1989). A GSMP formalism for discrete event systems. Proceedings of the IEEE 77: 14–23.CrossRefGoogle Scholar
10.Glynn, P.W. (1994). Some topics in regenerative steady state simulation. Acta Applicandae Mathematicae 34: 225–236.CrossRefGoogle Scholar
11.Glynn, P.W. & Heidelberger, P. (1991). Analysis of parallel replicated simulations under a completion time constraint. ACM Transactions on Modeling and Computer Simulation 1: 3–23.CrossRefGoogle Scholar
12.Glynn, P.W. & Iglehart, D.L. (1987). A joint central limit theorem for the sample mean and regenerative variance estimator. Annals of Operations Research 8: 41–55.CrossRefGoogle Scholar
13.Glynn, P.W. & L'Ecuyer, P. (1995). Likelihood ratio gradient estimation for stochastic recursions. Advances in Applied Probability (to appear).CrossRefGoogle Scholar
14.Glynn, P.W. & Wong, E. (1996). Efficient simulation via coupling. Technical Report (in preparation).CrossRefGoogle Scholar
15.Iglehart, D.L. & Shedler, G.S. 1980. Regenerative simulation of response times in networks of queues. Berlin: Springer-Verlag.CrossRefGoogle Scholar
16.Lindvall, T. (1992). Lectures on the coupling method. New York: Wiley.Google Scholar
17.Meketon, M.S. & Heidelberger, P. (1982). A renewal theoretic approach to bias reduction in regenerative simulations. Management Science 28: 173–181.CrossRefGoogle Scholar
18.Meyn, S.P. & Tweedie, R.L. (1993). Markov chains and stochastic stability. New York: Springer-Verlag.CrossRefGoogle Scholar
19.Mykland, P., Tierney, L., & Yu, B. (1992). Regeneration in Markov chain samplers. Technical Report 585, School of Statistics, University of Minnesota.Google Scholar
20.Nummelin, E. (1978). A splitting technique for Harris recurrent Markov chains. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 43: 309–318.CrossRefGoogle Scholar
21.Orey, S. (1971). Limit theorems for Markov chain transition probabilities. London: Van Nostrand Reinhold.Google Scholar
22.Royden, H. (1988). Real analysis. New York: Macmillan.Google Scholar
23.Shahabuddin, P. (1994). Efficient simulation of regenerative systems whose steady state measure is known. Research Report 19658, IBM Watson Research Center, Yorktown Heights, NY.Google Scholar
24.Thorisson, H. (1992). Construction of a stationary regenerative process. Stochastic Processes and Their Applications 42: 237–253.CrossRefGoogle Scholar