A Large Deviations Perspective on the Efficiency of Multilevel Splitting

Copyright [©] (1998) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

Stringent performance standards for computing and telecommunications systems have motivated the development of efficient techniques for estimating rare event probabilities. In this paper, we analyze the performance of a multilevel splitting method for rare event simulation related to one recently proposed in the telecommunications literature. This method splits promising paths into subpaths at intermediate levels to increase the number of observations of a rare event. In a previous paper we gave sufficient conditions, in specific classes of models, for this method to be asymptotically optimal; here we focus on necessary conditions in a general setting. We show, through a variety of results, the importance of choosing the intermediate thresholds in a way consistent with the most likely path to a rare set, both when the number of levels is fixed and when it increases with the rarity of the event. In the latter case, we give very general necessary conditions based on large deviations rate functions. These indicate that even when the intermediate levels are chosen appropriately, the method will frequently fail to be asymptotically optimal. We illustrate the conditions with examples.

By: Paul Glasserman (Columbia Univ.), Philip Heidelberger, Perwez Shahabuddin (Columbia Univ.) and Tim Zajic (Columbia Univ.)

Published in: IEEE Transactions on Automatic Control, volume 43, (no 12), pages 1666-79 in 1998

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .