University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

      Fast simulation of rare events in Markov level/phase processes

      Thumbnail
      View/Open
      Luo-dissertat.pdf (1.031Mb)
      Date
      2004-05-05
      Author
      Luo, Jingxiang
      Type
      Thesis
      Degree Level
      Doctoral
      Metadata
      Show full item record
      Abstract
      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.
      Degree
      Doctor of Philosophy (Ph.D.)
      Department
      Computer Science
      Program
      Computer Science
      Supervisor
      Grassmann, Winfried K.
      Committee
      Shahabuddin, Perwez; Neufeld, Eric; Makaroff, Dwight; Srinivasan, Raj
      Copyright Date
      May 2004
      URI
      http://hdl.handle.net/10388/etd-07152004-204729
      Subject
      performance analysis method
      rare event simulation
      large deviation
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy