A large deviations perspective on the efficiency of multilevel splitting

Stringent performance standards for computing and telecommunications system s have motivated the development of efficient techniques for estimating rar e event probabilities. In this paper, we analyze the performance of a multi level splitting method for rare event simulation related to one recently pr oposed in the telecommunications literature. This method splits promising p aths into subpaths at intermediate levels to increase the number of observa tions of a rare event. In a previous paper we gave sufficient conditions, i n specific classes of models, for this method to be asymptotically optimal; here we focus on necessary conditions in a general setting. We show, throu gh a variety of results, the importance of choosing the intermediate thresh olds 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. Tn the latter case, we give very general necessary conditions based on large deviations rate functions. These indicate that even when the inte rmediate levels are chosen appropriately, the method will frequently fail t o be asymptotically optimal. We illustrate the conditions with examples.