Computational Efficiency Evaluation in Output Analysis
H. Damerdji, S.G. Henderson, and P. W. Glynn
Proceedings of the 1997 Winter Simulation Conference, 208-215 (1997)
A central quantity in steady-state simulation is the time-average variance constant. Estimates of this quantity are needed (for example) for constructing condence intervals, and several estimators have been proposed, including nonoverlapping and overlapping batch means methods, spectral methods, and the regenerative method. The asymptotic statistical properties of these estimators have been investigated but the computational complexity involved in computing them has received very little attention.
We assume a fixed simulation run-length, as opposed to sequential methods in which the run-length is determined dynamically. In order to consistently estimate the time-average variance constant, all of the estimators require an amount of computation that is linear in the time-horizon simulated, with the exception of spectral methods which require a superlinear amount of computation.