NDLI: Using permutations in regenerative simulations to reduce variance

Content Provider	ACM Digital Library
Author	Calvin, James M. Nakayama, Marvin K.
Copyright Year	1998
Abstract	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.
Starting Page	153
Ending Page	193
Page Count	41
File Format	PDF
ISSN	10493301
e-ISSN	15581195
DOI	10.1145/280265.280273
Volume Number	8
Issue Number	2
Journal	ACM Transactions on Modeling and Computer Simulation (TOMACS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1998-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Efficiency improvement Permutations Regenerative simulation Variance reduction
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exploiting regenerative structure to estimate finite time averages via simulation

The semi-regenerative method of simulation output analysis

Simulation output analysis using integrated paths

Resampled Regenerative Estimators

Simulation output analysis using integrated paths II: Low bias estimators

On the efficiency of RESTART for multidimensional state systems

Variance estimation and sequential stopping in steady-state simulations using linear regression

Variance reduction through smoothing and control variates for Markov chain simulations

Confidence Intervals for Quantiles Using Sectioning When Applying Variance-Reduction Techniques

Using permutations in regenerative simulations to reduce variance

Similar Documents

Exploiting regenerative structure to estimate finite time averages via simulation

The semi-regenerative method of simulation output analysis

Simulation output analysis using integrated paths

Resampled Regenerative Estimators

Simulation output analysis using integrated paths II: Low bias estimators

On the efficiency of RESTART for multidimensional state systems

Variance estimation and sequential stopping in steady-state simulations using linear regression

Variance reduction through smoothing and control variates for Markov chain simulations

Confidence Intervals for Quantiles Using Sectioning When Applying Variance-Reduction Techniques

Using permutations in regenerative simulations to reduce variance