Using permutations in regenerative simulations to reduce variance
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 is proposed. To construct this new experiment, the authors 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. This strictly reduces variance when the original 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 explicit formulas for these new estimators are derived. Small sample behavior of the estimators is examined. In particular, it is proved that for any fixed number of cycles from the first regenerative sequence, the new estimator has smaller mean squared error than the standard estimator. It is explicitly shown that the 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. The paper itself is organized as follows. In Section 2 the assumptions are discussed. The basic idea of how to construct the new estimator is in Section 3. Section 4 contains a more formal description of the method. Section 5 describes the new method for the second moment of the cumulative reward over a regenerative cycle and shows how these results can be used to derive a new estimator in the variance parameter arising in regenerative simulation. In Section 6 new estimators for the expected cumulative reward until some sets of states is hit are derived. Storage and computational costs of the new estimator are analyzed in Section 7. The results of some simulation experiments comparing the new estimator with the standard ones are presented in Section 8. Section 9 discusses directions for future research. Finally, the pseudocode of one of the algorithms suggested in the paper together with most of the proofs are collected in an Appendix.
- Correlation-inducing variance reduction in regenerative simulation
- Permuted derivative and importance-sampling estimators for regenerative simulations.
- Variance reduction for sensitivity estimates obtained from regenerative simulation
- Using Rademacher permutations to reduce randomness
- A perspective on variance reduction in dynamic simulation experiments
- Applications of permutations to the simulations of critical values
- scientific article; zbMATH DE number 108577
- Variance Reduction in Simulation via Random Hazards
- Variance reduction methods for CONNFFESSIT-like simulations
- Permuted derivative and importance-sampling estimators for regenerative simulations.
- Correlation-inducing variance reduction in regenerative simulation
- Simulation of processes with multiple regeneration sequences
- Derandomizing variance estimators
- Accelerated regeneration for Markov chain simulations
- Improved estimates and confidence intervals for regenerative simulation
- ASYMPTOTIC VARIANCE OF PASSAGE TIME ESTIMATORS IN MARKOV CHAINS
- Exploiting regenerative structure to estimate finite time averages via simulation
- Resampled regenerative estimators
- Permuted Standardized Time Series for Steady-State Simulations
- Using Rademacher permutations to reduce randomness
- Fast random integer generation in an interval
This page was built for publication: Using permutations in regenerative simulations to reduce variance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4241212)
