Using Permutations in Regenerative Simulations to Reduce Variance

We propose a new estimator for a large class of performance measures obtained from a regenerative simulation of a system having two distinct sequences of regeneration times. To construct our new estimator, we first generate a sample path of a fixed number of cycles based on one sequence of regeneration times, divide the path into segments based on the second sequence of regeneration times, permute the segments, and calculate the performance on the new path using the first sequence of regeneration times, We average over all possible permutations to construct the new estimator. This strictly reduces variance when the original estimator is not simply an additive functional of the sample path. To use the new estimator in practice, the extra computational effort is not large since all permutations do not actually have to be computed as we derive explicit formulas for our new estimators. We examine the small-sample behavior of our estimators. In particular, we prove that for any fixed number of cycles from the first regenerative sequence, our new estimator has smaller mean squared error than the standard estimator. We show explicitly that our method can be used to derive new estimators for the expected cumulative reward until a certain set of states is hit, and the time-average variance parameter of a regenerative simulation.