Using Permutations in Regenerative Simulations to Reduce Variance

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)153-193
Number of pages41
JournalACM Transactions on Modeling and Computer Simulation
Issue number2
StatePublished - Apr 1998

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computer Science Applications


  • Efficiency improvement
  • Permutations
  • Regenerative simulation
  • Variance reduction


Dive into the research topics of 'Using Permutations in Regenerative Simulations to Reduce Variance'. Together they form a unique fingerprint.

Cite this