Abstract
The main focus of this thesis is rare event simulation for nonMarkovian tandem queues with i.i.d. arrival process and lighttailed 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 stateindependent change of measure and we show that this change of measure is the only exponential stateindependent 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 statedependent importance sampling. Based on the subsolution approach, we present a statedependent 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 statedependent importance sampling for Markovian tandem queues and we explore the possibilities for a statedependent 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.
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 stateindependent change of measure and we show that this change of measure is the only exponential stateindependent 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 statedependent importance sampling. Based on the subsolution approach, we present a statedependent 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 statedependent importance sampling for Markovian tandem queues and we explore the possibilities for a statedependent 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.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  21 Jun 2019 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036547888 
DOIs  
Publication status  Published  21 Jun 2019 
Fingerprint Dive into the research topics of 'Rare event simulation for nonMarkovian tandem queues'. Together they form a unique fingerprint.
Cite this
Buijsrogge, A. (2019). Rare event simulation for nonMarkovian tandem queues. Enschede: University of Twente. https://doi.org/10.3990/1.9789036547888