ABSTRACT [-]
There are many practical problems that involve the evaluation of rare-event probabilities. For example, in aviation, many international safety standards are stated as maximum rare-event probabilities, such as 10-7 fatal accidents per flight hour or 10-8 fatal accidents per operation during take-off or landing. The objective of this research is to present optimal simulation techniques, based on the concept of level splitting, to reduce the variance in estimating rare-event probabilities. The methods are presented both for evaluating a single system and for comparing two different systems against each other.

Without special techniques, the amount of computer time required to simulate rare-event problems may be prohibitive. For example, to simulate an event that occurs with probability 10-9 requires 109 simulation runs to observe one event, on average. To estimate the probability with a 1% relative error (that is, where the standard deviation of the estimator is 1% of the rare-event probability) requires 1013 simulation runs. If one can conduct 1,000 simulation runs per second, this would take over 30 years to compute.

The basic idea of splitting is to create separate copies (splits) of the simulation whenever it gets close to the rare event. This tends to allocate more computing time towards “promising" simulation runs. However, determination of a good number of splits at each level can be challenging. One approach is to simply use an equal number of splits at all levels. However, this may compromise the efficiency and can even increase the estimation variance. We formulate 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 available. We derive a solution that is asymptotically optimal as the computing budget goes to infinity. We provide approximate theoretical results for the improvements that are achievable using the methods. We also extend the idea to the problem of choosing the best of two designs, where both designs must be estimated via rare-event simulation.

We apply our method to a standard tandem queueing problem that has been considered in the literature. Numerical experiments indicate that our proposed approach is efficient and robust. The method is robust in the sense that it can be implemented on a computer independently from the choice of the levels. Typically, a good choice of levels is made on a problem-by-problem basis. Having a robust method that improves simulation performance regardless of this choice can be an advantage when modeling complex systems where it may be difficult to make these choices based purely on theoretical grounds.

Finally, we apply our methods to simulations of power grids in order to estimate blackout probabilities. The simulations consider network perturbations, hidden failures, and cascading outages.

ABSTRACT [-]
Simulation is a popular tool for analyzing large, complex, stochastic engineering systems, since closed-form analytical solutions generally do not exist for such problems and simulation is able to take into account the multi-events, multi-threats and cascading effects. When applying simulation to problem of protecting critical infrastructures, we face a computational challenge: some rare-event probabilities must be estimated in simulation, because the events of our major interest, for example, the blackout in electric grid, are going to occur with very low probability. A huge number of simulation replications may be needed in order to obtain a reasonable estimate of such a rare-event probability. Simulation efficiency is still a big concern. In this paper, we present an effective rare-event simulation technique and show that our technique can enhance the simulation efficiency by orders of magnitude. We also discuss its application to two critical infrastructure problems: cyber security and electric grid. Our proposed simulation approach is generic enough for many other rare-event problems.

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 multi-level splitting has emerged as a promising variance reduction technique. The basic idea of splitting is to create separate copies (splits) of the simulation whenever it gets close to the rare event. However, determination of a good number of splits at each level can be challenging. Some level splitting methods simply use an equal number of splits at all levels, which may compromise the efficiency. We formulate the problem of determining the number of splits in an optimization problem that minimizes the variance of an estimator subject to a constraint on the total computing budget available. We derive a solution that is asymptotically optimal as the computing budget goes to infinity. Then, we extend the idea to the problem of choosing the best of two designs, where both designs must be estimated via rare-event simulation. We provide approximate theoretical results for the improvements that are achievable using the methods. Numerical experiments indicate that the proposed approaches are effective.

ABSTRACT [-]
Efficiency is a big concern when using simulation to estimate rare-event probabilities, since a huge number of simulation replications may be needed in order to obtain a reasonable estimate of such a probability. Furthermore, when multiple designs must be compared, and each design requires simulation of a rare event, then the total number of samples across all designs can be prohibitively high. This paper presents a new approach to enhance the efficiency for rare-event simulation. Our approach is developed by integrating the notions of level splitting and optimal computing budget allocation. The goal is to determine the optimal numbers of simulation runs across designs and across a number of splitting levels so that the variance of the rare-event estimator is minimized.