Multilevel Splitting for Estimating Rare Event Probabilities

Paul Glasserman, Philip Heidelberger, Perwez Shahabuddin and Tim Zajic
Additional contact information
Paul Glasserman: 403 Uris Hall, Columbia Business School, New York, New York 10027
Philip Heidelberger: IBM T. J. Watson Research Center, P. O. Box 218, Yorktown Heights, New York 10598
Perwez Shahabuddin: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Tim Zajic: Lockheed Martin, P. O. Box 64525, MS U1P28, St. Paul, Minnesota 55164

Operations Research, 1999, vol. 47, issue 4, 585-600

Abstract: We analyze the performance of a splitting technique for the estimation of rare event probabilities by simulation. A straightforward estimator of the probability of an event evaluates the proportion of simulated paths on which the event occurs. If the event is rare, even a large number of paths may produce little information about its probability using this approach. The method we study reinforces promising paths at intermediate thresholds by splitting them into subpaths which then evolve independently. If implemented appropriately, this has the effect of dedicating a greater fraction of the computational effort to informative runs. We analyze the method for a class of models in which, roughly speaking, the number of states through which each threshold can be crossed is bounded. Under additional assumptions, we identify the optimal degree of splitting at each threshold as the rarity of the event increases: It should be set so that the expected number of subpaths reaching each threshold remains roughly constant. Thus implemented, the method is provably effective in a sense appropriate to rare event simulations. These results follow from a branching-process analysis of the method. We illustrate our theoretical results with some numerical examples for queueing models.

Keywords: simulation; efficiency; simulation of rare events by splitting; queues; simulation; simulation of rare events in queues (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.4.585 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:4:p:585-600

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().