The focus of this dissertation is on the simulation of rare events encountered in the performance analysis of queuing and reliability models. The probabilities of these events, though small, are significant with respect to accurate estimation of some commonly used performance parameters, e.g. mean time to system failure. Often, these probabilities cannot be found using analytic or numerical methods and Monte Carlo simulation is the only feasible solution approach. Importance sampling is a change-of-measure technique for speeding up the simulation of rare events, thus facilitating the estimation of their probabilities.; This dissertation concentrates on Markovian models and develops methods of finding the optimal (zero-variance) I.S. scheme in a form amenable for simulation for two classes of problems. These involve estimating either mean hitting (first passage) times or average fixed horizon costs. As knowledge of the optimal I.S. scheme implies knowledge of the probability to be estimated via simulation, for models complex enough to warrant a simulation solution for this probability these methods may not be computationally attractive. However, they can lead to useful insight into the construction of computationally attractive I.S. schemes.; Specifically, the methods of finding the optimal scheme lead to some guidelines for construction of good I.S. schemes. One of the methods developed also leads to analytic formula for computing the variance of the estimate from an arbitrary Markovian I.S. scheme for both problem classes. These formula can be used to experiment with different I.S. schemes without actually implementing them in a simulation. Also, for the hitting time problem, heuristic approximations of these methods lead to two new I.S. schemes for the tandem two station queue. Both these schemes improve on a scheme in the literature for a large range of values of the parameters (simulation inputs) of the original system.; Other contributions of this research include the standardization of definitions relating to the asymptotic behavior of I.S. estimates and the identification of some ambiguities in a heuristic approach in the literature for constructing I.S. schemes for queuing networks.
展开▼
