Methods of efficient Monte-Carlo simulation when rare events are involved have been studied for several decades. Rare events are very important in the context of evaluating high quality computer/communication systems. Meanwhile, the efficient simulation of systems involving rare events poses great challenges.
A simulation method is said to be efficient if the number of replicas required to get accurate estimates grows slowly, compared to the rate at which the probability of the rare event approaches zero.
Despite the great success of the two mainstream methods, importance sampling (IS) and importance splitting, either of them can become inefficient under certain conditions, as reported in some recent studies.
The purpose of this study is to look for possible enhancement of fast simulation methods. I focus on the ``level/phase process', a Markov process in which the level and the phase are two state variables. Furthermore, changes of level and phase are induced by events, which have rates that are independent of the level except at a boundary.
For such a system, the event of reaching a high level occurs rarely, provided the system typically stays at lower levels. The states at those high levels constitute the rare event set.
Though simple, this models a variety of applications involving rare events.
In this setting, I have studied two efficient simulation methods, the rate tilting method and the adaptive splitting method, concerning their efficiencies.
I have compared the efficiency of rate tilting with several previously used similar methods. The experiments are done by using queues in tandem, an often used test bench for the rare event simulation. The schema of adaptive splitting has not been described in literature. For this method, I have analyzed its efficiency to show its superiority over the (conventional) splitting method.
The way that a system approaches a designated rare event set is called the system's large deviation behavior. Toward the end of gaining insight about the relation of system behavior and the efficiency of IS simulation, I quantify the large deviation behavior and its complexity.
This work indicates that the system's large deviation behavior has a significant impact on the efficiency of a simulation method.
| Identifer | oai:union.ndltd.org:USASK/oai:usask.ca:etd-07152004-204729 |
| Date | 19 July 2004 |
| Creators | Luo, Jingxiang |
| Contributors | Shahabuddin, Perwez, Neufeld, Eric, Makaroff, Dwight, Grassmann, Winfried K., Srinivasan, Raj |
| Publisher | University of Saskatchewan |
| Source Sets | University of Saskatchewan Library |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://library.usask.ca/theses/available/etd-07152004-204729/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Saskatchewan or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0013 seconds