Efficient computation of overlapping variance estimators for simulation

For a steady–state simulation output process, we formulate efficient algorithms to compute certain estimators of the process variance parameter (i.e., the sum of covariances at all lags), where the estimators are derived in principle from overlapping batches separately and then averaged over all such batches. The algorithms require order–of–sample–size work to evaluate overlapping versions of the area and Cramér–von Mises estimators arising in the method of standardized time series. Recently, Alexopoulos et al. showed that, compared with estimators based on nonoverlapping batches, the estimators based on overlapping batches achieve reduced variance while maintaining similar bias asymptotically as the batch size increases. We provide illustrative analytical and Monte Carlo results for M/M/1 queue waiting times and for a first–order autoregressive process. We also present evidence that the asymptotic distribution of each overlapping variance estimator can be closely approximated using an appropriately rescaled chi–squared random variable with matching mean and variance.