On state-independent importance sampling for the GI|GI|1 tandem queue

Anne Buijsrogge (Corresponding Author), Pieter-Tjerk de Boer, Willem R.W. Scheinhardt

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
31 Downloads (Pure)

Abstract

In this paper, we consider a d-node GI|GI|1 tandem queue with i.i.d. inter-arrival process and service processes that are independent of each other. Our main interest is to estimate the probability to reach a high level N in a busy cycle of the system using simulation. As crude simulation does not give a sufficient precision in reasonable time, we use importance sampling. We introduce a method to find a state-independent change of measure and we show that this is equivalent to a change of measure that was earlier, but implicitly, described by Parekh and Walrand [8]. We also show that this change of measure is the only exponential state-independent change of measure that may result in an asymptotically efficient estimator. Lastly, we provide necessary conditions for this state-independent change of measure to give an asymptotically efficient estimator.
Original languageEnglish
Number of pages26
JournalProbability in the engineering and informational sciences
DOIs
Publication statusPublished - 5 Nov 2018

Fingerprint

Tandem Queues
Change of Measure
Importance sampling
Importance Sampling
Efficient Estimator
System Simulation
Change of measure
Queue
Sufficient
Cycle
Necessary Conditions
Vertex of a graph
Estimate
Simulation

Keywords

  • UT-Hybrid-D
  • Tandem queue
  • Rare event simulation
  • Importance sampling
  • GI|GI|1 queue

Cite this

@article{608f4d96e6d44d66aaee07447c6b18f3,
title = "On state-independent importance sampling for the GI|GI|1 tandem queue",
abstract = "In this paper, we consider a d-node GI|GI|1 tandem queue with i.i.d. inter-arrival process and service processes that are independent of each other. Our main interest is to estimate the probability to reach a high level N in a busy cycle of the system using simulation. As crude simulation does not give a sufficient precision in reasonable time, we use importance sampling. We introduce a method to find a state-independent change of measure and we show that this is equivalent to a change of measure that was earlier, but implicitly, described by Parekh and Walrand [8]. We also show that this change of measure is the only exponential state-independent change of measure that may result in an asymptotically efficient estimator. Lastly, we provide necessary conditions for this state-independent change of measure to give an asymptotically efficient estimator.",
keywords = "UT-Hybrid-D, Tandem queue, Rare event simulation, Importance sampling, GI|GI|1 queue",
author = "Anne Buijsrogge and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.}",
note = "Cambridge UP deal",
year = "2018",
month = "11",
day = "5",
doi = "10.1017/S0269964818000426",
language = "English",
journal = "Probability in the engineering and informational sciences",
issn = "0269-9648",
publisher = "Cambridge University Press",

}

On state-independent importance sampling for the GI|GI|1 tandem queue. / Buijsrogge, Anne (Corresponding Author); de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W.

In: Probability in the engineering and informational sciences, 05.11.2018.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On state-independent importance sampling for the GI|GI|1 tandem queue

AU - Buijsrogge, Anne

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

N1 - Cambridge UP deal

PY - 2018/11/5

Y1 - 2018/11/5

N2 - In this paper, we consider a d-node GI|GI|1 tandem queue with i.i.d. inter-arrival process and service processes that are independent of each other. Our main interest is to estimate the probability to reach a high level N in a busy cycle of the system using simulation. As crude simulation does not give a sufficient precision in reasonable time, we use importance sampling. We introduce a method to find a state-independent change of measure and we show that this is equivalent to a change of measure that was earlier, but implicitly, described by Parekh and Walrand [8]. We also show that this change of measure is the only exponential state-independent change of measure that may result in an asymptotically efficient estimator. Lastly, we provide necessary conditions for this state-independent change of measure to give an asymptotically efficient estimator.

AB - In this paper, we consider a d-node GI|GI|1 tandem queue with i.i.d. inter-arrival process and service processes that are independent of each other. Our main interest is to estimate the probability to reach a high level N in a busy cycle of the system using simulation. As crude simulation does not give a sufficient precision in reasonable time, we use importance sampling. We introduce a method to find a state-independent change of measure and we show that this is equivalent to a change of measure that was earlier, but implicitly, described by Parekh and Walrand [8]. We also show that this change of measure is the only exponential state-independent change of measure that may result in an asymptotically efficient estimator. Lastly, we provide necessary conditions for this state-independent change of measure to give an asymptotically efficient estimator.

KW - UT-Hybrid-D

KW - Tandem queue

KW - Rare event simulation

KW - Importance sampling

KW - GI|GI|1 queue

U2 - 10.1017/S0269964818000426

DO - 10.1017/S0269964818000426

M3 - Article

JO - Probability in the engineering and informational sciences

JF - Probability in the engineering and informational sciences

SN - 0269-9648

ER -