On Efficiency of Multilevel Splitting

Abstract

This article focuses on estimating rare events using multilevel splitting schemes. The event of interest is that a Markov process enters some rare set before another (“tabu”) set. It is known that in this setting a large deviations analysis is not always sufficient for constructing asymptotically efficient importance sampling schemes; additional modifications to the change of measure suggested by large deviations are needed. As an alternative, we design an asymptotically efficient multilevel splitting scheme that relies on the large deviations analysis only. This property makes it more flexible and easier to implement than corresponding importance sampling schemes.

Keywords:

• Asymptotic efficiency
• Fast simulation techniques
• Queueing networks
• Server slowdown
• Splitting method
• Variance reduction

Mathematics Subject Classification:

• 60K25
• 60J22
• 65C05

Acknowledgment

Part of this research has been funded by the Dutch BSIK/BRICKS project. This article is also the result of joint research in the 3 TU Centre of Competence Netherlands Institute for Research on ICT within the Federation of Three Universities of Technology in The Netherlands.

Notes

Formally the state space is a subset of D (namely a grid) for any finite B. As B grows large, the grid becomes denser, leading to D itself in the limit B → ∞.