Abstract:
This dissertation develops efficient algorithms, in theory and in implementation, for selecting, via simulation, the best design, or system, from a set of designs, where “best” is the design with the smallest probability of some (generally undesirable) outcome. Compared to standard techniques these algorithms improve the efficiency of simulation when the (undesirable) outcomes have very small probabilities, on the order of 1.0E-6, or smaller. Such outcomes are “rare events”. The algorithms could also be used to estimate non-rare probabilities, although, in that case, their advantages over techniques not geared toward rare events diminish.
The designs in question differ in construction, or in the values of their parameters, but are such that their operations can be simulated as stochastic processes which terminate in a non-rare event (a set of non-rare outcomes), or a rare event (a set of rare outcomes). The task is to estimate, efficiently, the probabilities of the rare events, in order to select the design with the smallest one. Efficient algorithms are those which produce estimators of the rare event probabilities with acceptable variances, within acceptable computational times. I do not define “acceptable variances”. The focus is on algorithms which achieve better results, compared to standard methods, for a given amount of computational time (a given computing budget constraint). Better results are achieved by (approximately) maximizing the Probability of Correct Selection (PCS) of an algorithm, subject to a computing budget constraint. PCS is the probability that the algorithm will correctly identify the best design.
Simulation algorithms against which the new algorithms are compared include simple Monte Carlo (MC), Optimal Computing Budget Allocation (OCBA), fixed-effort Splitting, and the Optimal Splitting Technique for Rare-Event Simulation (OSTRE). These algorithms are reviewed, prior to the development of the two new algorithms: Single Optimization and OCBA+OSTRE.
The major contribution of this dissertation is the theoretical development and practical implementation of these new algorithms. The mathematical equivalence of these two new methods (in the sense that they attain, in theory, the same maximum PCS) is proven, and their computational complexities are compared. Numerical testing illustrates that they can out-perform standard techniques, and suggests that OCBA+OSTRE is better, in practice, than Single Optimization.
