This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Juneja, S. Search for Related Content

Importance Sampling and the Cyclic Approach

Department of Mechanical Engineering, Indian Institute of Technology, Delhi, Hauz Khas, New Delhi 110016, India
sandeepj{at}mech.iitd.ernet.in

The method of importance sampling is widely used for efficient rare-event simulation of stochastic systems. This method involves simulating the system under a new distribution that accentuates the probability along the most likely paths to the rare event. Traditionally, insights from large deviations theory are used to identify the distribution emphasizing these most likely paths. In this paper we develop an intuitive cyclic approach for selecting such a distribution. The key idea is to select a distribution under which the event of interest is no longer rare and the probability of occurrence of a cycle in any sample path remains equal to the original probability of that cycle. We show that only an exponentially twisted distribution can satisfy this equiprobable cycle condition. Using this approach we provide an elementary derivation of the asymptotically optimal change of measure for level crossing probability for Markov-additive processes. To demonstrate its ease of use for more complex stochastic systems, we apply it to determine the asymptotically optimal change of measure for estimating buffer overflow probability of a single-server queue subject to server interruptions.

Subject classifications: Markov processes; Simulation: importance sampling.
History: Received March 1994; revision received August 1998; revision received December 1999; revision received June 2000; accepted June 2000.