Rare event simulation for non-Markovian tandem queues

Anne Buijsrogge

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

22 Downloads (Pure)

Abstract

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.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Boucherie, Richardus J., Supervisor
  • Haverkort, Boudewijn R.H.M., Supervisor
  • de Boer, Pieter-Tjerk , Co-Supervisor
  • Scheinhardt, Willem R.W., Co-Supervisor
Thesis sponsors
Award date21 Jun 2019
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4788-8
DOIs
Publication statusPublished - 21 Jun 2019

Fingerprint

Rare Event Simulation
Tandem Queues
Change of Measure
Importance Sampling
Efficient Estimator
Large Deviations
Customers
Subsolution
Probability Distribution
Dependent
Simulation
Interval
Stationarity
Estimate
Queue
Stochastic Processes
Speedup
Continue

Cite this

Buijsrogge, Anne . / Rare event simulation for non-Markovian tandem queues. Enschede : University of Twente, 2019. 182 p.
@phdthesis{e0dd3d9238ca4dcc853f7e352c919818,
title = "Rare event simulation for non-Markovian tandem queues",
abstract = "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.",
author = "Anne Buijsrogge",
year = "2019",
month = "6",
day = "21",
doi = "10.3990/1.9789036547888",
language = "English",
isbn = "978-90-365-4788-8",
series = "DSI Ph.D. Thesis Series",
publisher = "University of Twente",
number = "008",
address = "Netherlands",
school = "University of Twente",

}

Buijsrogge, A 2019, 'Rare event simulation for non-Markovian tandem queues', Doctor of Philosophy, University of Twente, Enschede. https://doi.org/10.3990/1.9789036547888

Rare event simulation for non-Markovian tandem queues. / Buijsrogge, Anne .

Enschede : University of Twente, 2019. 182 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Rare event simulation for non-Markovian tandem queues

AU - Buijsrogge, Anne

PY - 2019/6/21

Y1 - 2019/6/21

N2 - 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.

AB - 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.

U2 - 10.3990/1.9789036547888

DO - 10.3990/1.9789036547888

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4788-8

T3 - DSI Ph.D. Thesis Series

PB - University of Twente

CY - Enschede

ER -

Buijsrogge A. Rare event simulation for non-Markovian tandem queues. Enschede: University of Twente, 2019. 182 p. (DSI Ph.D. Thesis Series ; 008). https://doi.org/10.3990/1.9789036547888