Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/246387 
Year of Publication: 
2019
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 6 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2019 [Pages:] 1-9
Publisher: 
Elsevier, Amsterdam
Abstract: 
RESTART is a widely applicable accelerated simulation technique that allows the evaluation of extremely low probabilities. In this method a number of retrials (or paths) are made when the process reaches certain thresholds of a function of the system state, called the importance function. In RESTART with prolonged retrials, all but one path are cut when they drop several thresholds (rather than when they down-cross the threshold that they started from). The only path that continues collects the weight of the cut paths to keep the estimator unbiased. In this paper a theoretical analysis of this version of the method is made. First the variances of RESTART with prolonged retrials for different degrees of prolongation are compared. Then, formulas for the computational costs of these variants are derived. It is shown that by prolonging the retrials by one or two thresholds, a significant reduction of variance with respect to RESTART is obtained in models where many thresholds can be set (for example, in communication network models). This is attained with a similar or small additional computational cost per sample, so that the gain obtained may even exceed 50%. This gain, which is achieved with no additional effort, illustrates the interest of applying these variants. Greater degrees of prolongation are not advisable because, as the formulas show, any additional reduction of variance is small and does not compensate the additional cost per sample. This would explain the bad behaviour of standard Splitting compared with RESTART.
Subjects: 
Simulation
Rare event probabilities
Variance reduction
RESTART
Splitting
Queuing networks
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.