Optimal splitting for rare-event simulation

Abstract

Simulation is a popular tool for analyzing large, complex, stochastic engineering systems. When estimating rare-event probabilities, efficiency is a big concern, since a huge number of simulation replications may be needed in order to obtain a reasonable estimate of the rare-event probability. The idea of splitting has emerged as a promising variance reduction technique. The basic idea is to create separate copies (splits) of the simulation whenever it gets close to the rare event. Some splitting methods use an equal number of splits at all levels. This can compromise the efficiency and can even increase the estimation variance. This article formulates the problem of determining the number of splits as an optimization problem that minimizes the variance of an estimator subject to a constraint on the total computing budget. An optimal solution for a certain class of problems is derived that is then extended to the problem of choosing the better of two designs, where each design is evaluated via rare-event simulation. Theoretical results for the improvements that are achievable using the methods are provided. Numerical experiments indicate that the proposed approaches are efficient and robust.

Keywords:

• Rare-event simulation
• splitting
• comparison of designs