TY - JOUR
T1 - Large deviations and fast simulation in the presence of boundaries
AU - Asmussen, Søren
AU - Fuckerieder, Pascal
AU - Jobmann, Manfred
AU - Schwefel, Hans Peter
PY - 2002/11/1
Y1 - 2002/11/1
N2 - Let τ(x) = inf {t > 0: Q(t) ≥ x} be the time of first overflow of a queueing process {Q(t)} over level x (the buffer size) and z = ℙ(τ(x) ≤ T). Assuming that Q(t) is the reflected version of a Lévy process {X (t)} or a Markov additive process, we study a variety of algorithms for estimating z by simulation when the event {τ(x) ≤ T} is rare, and analyse their performance. In particular, we exhibit an estimator using a filtered Monte Carlo argument which is logarithmically efficient whenever an efficient estimator for the probability of overflow within a busy cycle (i.e., for first passage probabilities for the unrestricted netput process) is available, thereby providing a way out of counterexamples in the literature on the scope of the large deviations approach to rare events simulation. We also add a counterexample of this type and give various theoretical results on asymptotic properties of z=ℙ(τ(x) ≤ T), both in the reflected Lévy process setting and more generally for regenerative processes in a regime where T is so small that the exponential approximation for τ(x) is not a priori valid.
AB - Let τ(x) = inf {t > 0: Q(t) ≥ x} be the time of first overflow of a queueing process {Q(t)} over level x (the buffer size) and z = ℙ(τ(x) ≤ T). Assuming that Q(t) is the reflected version of a Lévy process {X (t)} or a Markov additive process, we study a variety of algorithms for estimating z by simulation when the event {τ(x) ≤ T} is rare, and analyse their performance. In particular, we exhibit an estimator using a filtered Monte Carlo argument which is logarithmically efficient whenever an efficient estimator for the probability of overflow within a busy cycle (i.e., for first passage probabilities for the unrestricted netput process) is available, thereby providing a way out of counterexamples in the literature on the scope of the large deviations approach to rare events simulation. We also add a counterexample of this type and give various theoretical results on asymptotic properties of z=ℙ(τ(x) ≤ T), both in the reflected Lévy process setting and more generally for regenerative processes in a regime where T is so small that the exponential approximation for τ(x) is not a priori valid.
KW - Buffer overflow
KW - Exponential change of measure
KW - Filtered Monte Carlo
KW - Importance sampling Lévy process
KW - Local time
KW - Queueing theory
KW - Rare event
KW - Reflection
KW - Regenerative process
KW - Saddlepoint
UR - http://www.scopus.com/inward/record.url?scp=0036829392&partnerID=8YFLogxK
U2 - 10.1016/S0304-4149(02)00152-7
DO - 10.1016/S0304-4149(02)00152-7
M3 - Journal article
AN - SCOPUS:0036829392
SN - 0304-4149
VL - 102
SP - 1
EP - 23
JO - Stochastic Processes and Their Applications
JF - Stochastic Processes and Their Applications
IS - 1
ER -