A large deviations perspective on the efficiency of multilevel splitting

Abstract

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 likey 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.