skip to main content
article

Exploiting regenerative structure to estimate finite time averages via simulation

Published: 01 April 2007 Publication History

Abstract

We propose nonstandard simulation estimators of expected time averages over finite intervals [0, t], seeking to enhance estimation efficiency. We make three key assumptions: (i) the underlying stochastic process has regenerative structure, (ii) the time average approaches a known limit as time t increases and (iii) time 0 is a regeneration time. To exploit those properties, we propose a residual-cycle estimator, based on data from the regenerative cycle in progress at time t, using only the data after time t. We prove that the residual-cycle estimator is unbiased and more efficient than the standard estimator for all sufficiently large t. Since the relative efficiency increases in t, the method is ideally suited to use when applying simulation to study the rate of convergence to the known limit. We also consider two other simulation techniques to be used with the residual-cycle estimator. The first involves overlapping cycles, paralleling the technique of overlapping batch means in steady-state estimation; multiple observations are taken from each replication, starting a new observation each time the initial regenerative state is revisited. The other technique is splitting, which involves independent replications of the terminal period after time t, for each simulation up to time t. We demonstrate that these alternative estimators provide efficiency improvement by conducting simulations of queueing models.

Supplementary Material

Kang Appendix (a8-kang-apndx.pdf)
Online appendix to designing mediation for context-aware applications. The appendix supports the information on article 8.

References

[1]
Asmussen, S. 2003. Applied Probability and Queues, second ed. Wiley, New York.
[2]
Billingsley, P. 1999. Convergence of Probability Measures, second ed. Wiley, New York.
[3]
Bratley, P., Fox, B. L., and Schrage, L. E. 1987. A Guide to Simulation, Second Ed. Springer Verlag, New York.
[4]
Calvin, J. M. and Nakayama, M. K. 1998. Using permutations in regenerative simulations to reduce variance. ACM Trans. Model. Comput. Simul. 8, 153--193.
[5]
Calvin, J. M. and Nakayama, M. K. 2000. Central limit theorems for permuted regenerative estimators. Oper. Res. 48, 776--787.
[6]
Chow, Y. S., Hsiung, C. A., and Lai, T. L. 1979. Extended renewal theory and moment convergence in Anscombe's theorem. Ann. Probab. 7, 304--318.
[7]
Chung, K. L. 1974. A Course in Probability Theory, second ed. Academic Press.
[8]
Crane, M. A. and Iglehart, D. L. 1975. Simulating stable stochastic systems III: regenerative processes and discrete event simulation. Oper. Res. 23, 33--45.
[9]
Duffield, N. G. and Whitt, W. 2000. Network design and control using on-off and multi-level source traffic models with heavy-tailed distributions. Chapter 17 in Self-Similar Network Traffic and Performance Evaluation, Kihong Park and Walter Willinger, eds. John Wiley and Sons, 421-445.
[10]
Erdélyi, A. 1956. Asymptotic Expansions, Dover.
[11]
Glynn, P. W. and Iglehart, D. L. 1986. Consequences of uniform integrability for simulation. Tech. rep. 40, Stanford University, Dept. of Operations Research.
[12]
Glynn, P. W. and Whitt, W. 1992. The Asymptotic Efficiency of Simulation Estimators. Oper. Res., 40, 505--520.
[13]
Glynn, P. W. and Whitt, W. 1993. Limit theorems for cumulative processes, Stoch. Proc. Appl. 47, 299--314.
[14]
Glynn, P. W. and Whitt, W. 2002. Necessary conditions in limit theorems for cumulative processes, Stoch. Proc. Appl. 98, 199--209.
[15]
Glynn, P. W. and Wong E. W. 1996. Efficient simulation via coupling. Prob. Engr. Inf. Sci. 10, 165--186.
[16]
Gut, A. 1988. Stopped Random Walks, Springer.
[17]
Hammersley, J. M. and Handscomb, D. C. 1964. Monte Carlo Methods, Methuen, London.
[18]
Henderson, S. G. and Glynn, P. W. 2002. Approximating martingales for variance reduction in Markov process simulation. Math. Opes. Res. 27, 253--271.
[19]
Kang, W., Shahabuddin, P., and Whitt, W. 2007. Exploiting regenerative structure to estimate finite time averages via simulation: supplementary material available in the ACM Digital Library.
[20]
Keilson, J. 1979. Markov Chain Models---Rarity and Exponentiality, Springer.
[21]
Meketon, M. S. and Heidelberger, P. 1982. A renewal theoretic approach to bias reduction in regenerative simulations. Manag. Sci. 28, 173--181.
[22]
Meketon, M. S. and Schmeiser, B. 1984. Overlapping batch means; something for nothing? Proceedings of 1984 Winter Simulation Conference, 227--230.
[23]
Meyn, S. P. and Tweedie, R. L. 1993. Markov Chains and Stochastic Stability, Springer.
[24]
Pawlikowski, K. 1990. Steady state simulation of queueing processes; a survey of problems and solutions. ACM Comput. Surv. 22, 123--170.
[25]
Ross, S. M. 1996. Stochastic Processes, second ed., John Wiley and Sons.
[26]
Ross, S. M. 2003. Introduction to Probability Models, eighth ed. Academic Press, New York.
[27]
Smith, W. L. 1955. Regenerative stochastic processes. Proceedings of the Royal Society of London A232, 6--31.
[28]
Whitt, W. 1972. Embedded renewal processes in the GI/G/s queue. J. Appl. Prob. 9, 650--658.
[29]
Whitt, W. 1992. Asymptotic formulas for Markov processes. Oper. Res. 40, 279--291.
[30]
Wong E. W., Glynn, P. W., and Iglehart, D. L. 1999. Transient simulation via empirically based coupling. Prob. Engr. Inf. Sci. 13, 147--167.

Cited By

View all
  • (2007)Perwez Shahabuddin, 1962--2005ACM Transactions on Modeling and Computer Simulation10.1145/1225275.122527717:2(6-es)Online publication date: 1-Apr-2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation
ACM Transactions on Modeling and Computer Simulation  Volume 17, Issue 2
April 2007
169 pages
ISSN:1049-3301
EISSN:1558-1195
DOI:10.1145/1225275
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2007
Published in TOMACS Volume 17, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Efficiency improvement
  2. regenerative processes
  3. time averages
  4. variance reduction

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2007)Perwez Shahabuddin, 1962--2005ACM Transactions on Modeling and Computer Simulation10.1145/1225275.122527717:2(6-es)Online publication date: 1-Apr-2007

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media