Stationarity detection in the initial transient problem

ABSTRACT

Let X = {X(t)}t ≥ 0 be a stochastic process with a stationary version X*. It is investigated when it is possible to generate by simulation a version X˜ of X with lower initial bias than X itself, in the sense that either X˜ is strictly stationary (has the same distribution as X*) or the distribution of X˜ is close to the distribution of X*. Particular attention is given to regenerative processes and Markov processes with a finite, countable, or general state space. The results are both positive and negative, and indicate that the tail of the distribution of the cycle length &tgr; plays a critical role. The negative results essentially state that without some information on this tail, no a priori computable bias reduction is possible; in particular, this is the case for the class of all Markov processes with a countably infinite state space. On the contrary, the positive results give algorithms for simulating X˜ for various classes of processes with some special structure on &tgr;. In particular, one can generate X˜ as strictly stationary for finite state Markov chains, Markov chains satisfying a Doeblin-type minorization, and regenerative processes with the cycle length &tgr; bounded or having a stationary age distribution that can be generated by simulation.

REFERENCES

• 1: ALDOUS, D. Meeting times for independent Markov chains. Stoch. Process. Appl. 38 (1991), 185-193.
• 2: ALDOUS D., AND DIACONIS, P. Shuffling cards and stopping times Am Moth. 93 (1986), 333 348.
• 3: David Aldous , Persi Diaconis, Strong uniform times and finite random walks, Advances in Applied Mathematics, v.8 n.1, p.69-97, March 1987 [doi>10.1016/0196-8858(87)90006-6]
• 4: ASMUSSEN, S. Apphed Probabd~ty and Queues. New York, 1987.
• 5: ASMUSSEN, S., AND THORISSON, H. A Markov chain approach to periodic queues. J. Appl. Probab. 24 (1987), 215-225.
• 6: ATHREYA, K. B., AND NEY, P. A new approach to the limit theory of recurrent Markov chains. Trans. Am. Math. Soc. 245 (1978), 493-501
• 7: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 8: CnUNG, K.L. A Course in Probability Theory. 2nd ed. Academic Press, New York, 1974.
• 9: CONWAY, R. W. Some tactical problems in digital simulation. Manage. Sct. 10 (1963), 47-61.
• 10: DooB, J.L. Stochastic Process. Wiley, New York, 1953.
• 11: George S. Fishman, Principles of Discrete Event Simulation, John Wiley & Sons, Inc., New York, NY, 1978
• 12: GAFARIAN, A. V., ANCKER, JR., C. J., AND MORISAKU, T. Evaluation of commonly used rules for detecting steady-state in computer simulation. Nav. Res. Logistics Q. 25 (1978), 511-529.
• 13: GLYNN, P.W. Regenerative simulation of Harris recurrent Markov chains. Tech. Rep. 18, Dept. of Operations Research, Stanford Univ., 1982.
• 14: GLYNN, P.W. A GSMP formalism for discrete event systems. Proc. IEEE 77, 1989, 14 23.
• 15: GLYN~, P. W,, AND IGLEU^RT, D.L. Conditions under which a Markov chain converges to its steady-state in finite time. Probab. Eng. Inf. Sci. 2 (1988), 377-382.
• 16: Peter W. Glynn , Ward Whitt, The asymptotic efficiency of simulation estimators, Operations Research, v.40 n.3, p.505-520, May–June 1992 [doi>10.1287/opre.40.3.505]
• 17: IGLEHART, D.L. The regenerative method for simulation analysis. In Current Trends in Programming Methodology, Chandy and Yeh, Eds., Prentice Hall, Englewood Cliffs, N.J., 1.978.
• 18: KEANE, M., AND O'BmEN, G.L. A Bernoulli factory. Manuscript~ 1992.
• 19: KELLY, F.P. Revers~bzhty and Stochastic Networks. Wiley, New York, 1979.
• 20: KELTON, W. D, AND LAW, A. M. A new approach for dealing with the startup problem in discrete event simulation. Oper. Res. 30 (1982), 641-658.
• 21: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 22: LINDVALL, T. Lectures on the Couphng Method. Wiley, New York, to appear, 1992.
• 23: NEUTS, M.F. Matrix-Geometric Soluttons zn Stochastic Models. Johns Hopkins University Press, Baltimore, Md., 1981.
• 24: ROLSKI, T. Stationary Random Processes Associated with Point Processes. Lecture Notes on Statistics 5. Springer-Verlag, New York, 1981.
• 25: SCHRUBEN, L.W. Detecting initialization bias in simulation output. Oper. Res. 30, 1982, 569 590.
• 26: T~omssoN, H.The coupling of regenerative processes. Adv. Appl. Probab. 15 (1983), 531 561.
• 27: THORISSON, H.Construction of a stationary regenerative process. Stoch. Proc. Appl. 1991.
• 28: THOmSSON, H.Time- and cycle stationarity, 1991. In preparation.
• 29: WELCrt, P. D.A graphical approach to the initial transient problem in steady state simulations. In Proceedings of the lOth IMACS World Congress on Systems, Simulation and Sctentifzc Computation (Montreal, 1982), pp. 219-221.
• 30: W~LCH, P.D. The statistical analysis of simulatmn results. In The Computer Performance Modeling Handbook, S. S. Lavenberg Ed. Academic Press, New York, 1983.
• 31: WHITT, W. Untold horrors of the waiting room' What the steady-state distribution will never tell. Manoge. Sci. 29 (1983), 395-408.
• 32: WILSON, J. R., AND PRiTSKER, A. A. B. A survey of research on the simulation startup problem. Simulation 31 (1978), 55-58.
• 33: WmsoN, J. R., ^ND PRITSKER, A. A.B. Evaluation of start-up policies in simulation experiments. Simulation 31 (1978), 79 89.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory

Keywords:
coupling, initial transient, regenerative processes, stationary processes