Accelerated Regeneration for Markov Chain Simulations

S. Andradóttir, J. M. Calvin, and P. W. Glynn

Probability in the Engineering and Informational Sciences, Vol. 9, 497-523, (1995)

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.