Derandomizing Variance Estimators

S. G. Henderson and P. W. Glynn

Operations Research. Vol. 47 (6), 907-916 (1999)

One may consider a discrete-event simulation as a Markov chain evolving on a suitably rich state space. One way that regenerative cycles may be constructed for general state-space Markov chains is to generate auxiliary coin-flip random variables at each transition, with a regeneration occurring if the coin-flip results in a success. The regenerative cycles are therefore randomized with respect to the sequence of states visited by the Markov chain. The point estimator for a steady-state performance measure does not depend on the cycle structure of the chain, but the variance estimator (that defines the width of a confidence interval for the performance measure) does. This implies that the variance estimatori s randomized with respect to the visited states. We show how to "derandomize"th e variance estimatort hrough the use of conditioning. A new variance estimator is obtained that is consistent and has lower variance than the standard estimator.