rare event simulation for non-markovian tandem queues
Anne Buijsrogge is a PhD student in the research group Mathematics of Operations Research (MOR). Her supervisors are prof.dr. R.J. Boucherie and prof.dr.ir. B.R.H.M. Haverkort from the faculty of Electrical Engineering, Mathematics and Computer Science.
The main focus of this thesis is rare event simulation for non-Markovian tandem queues with i.i.d. arrival process and light-tailed service processes that are independent of each other. We are interested in developing simulation schemes in order to estimate the probability that the total number of customers reaches some high number during a busy cycle of the system. As ordinary simulation does not give the desired estimate in reasonable time, we consider two methods in order to decrease the simulation time: importance sampling and splitting.
In order to use either of these methods, we first determine the large deviations behavior of the probability of interest. In addition, we show that the large deviations behavior of the probability of having a high number of customers in the system in stationarity, as well as upon arrival of a customer, are the same.
Secondly, we consider importance sampling. With importance sampling, we change the underlying probability distributions of the arrival process and service processes to speed up the simulation. The change of probability distributions is also called a change of measure. First, we discuss how to find a state-independent change of measure and we show that this change of measure is the only exponential state-independent change of measure that may give an asymptotically efficient estimator. Moreover, we provide necessary conditions for this change of measure to give an asymptotically efficient estimator. In order to find a change of measure that always gives an asymptotically efficient estimator, we consider state-dependent importance sampling. Based on the subsolution approach, we present a state-dependent change of measure and we prove that our proposed change of measure indeed gives an asymptotically efficient estimator.
Thirdly, we consider splitting. With splitting, we keep the underlying probability distributions the same, but we `encourage' the process when it tends into the right direction, that is, when the process crosses some predetermined thresholds, the process splits into several independent processes that all continue according to the same dynamics as the original process. We develop splitting thresholds using the same underlying methods as for designing the importance sampling schemes and we prove that the proposed splitting thresholds result in an asymptotically efficient estimator.
In the course of the analysis, we also consider three different, but related topics. The first is to study the large deviations behavior of the probability of interest when customer sizes differ in each of the queues. Secondly, we study state-dependent importance sampling for Markovian tandem queues and we explore the possibilities for a state-dependent change of measure using subsolutions. Lastly, we determine for a rather general class of stochastic processes the large deviations behavior of the probability that the process leaves a neighborhood of a metastable point during some long time interval [0, T] when the time interval depends on the rarity parameter.