Advanced

Large deviations and fast simulation in the presence of boundaries

Asmussen, Sören LU ; Fuckerieder, P; Jobmann, M and Schwefel, HP (2002) In Stochastic Processes and their Applications 102(1). p.1-23
Abstract
Let c(x) = inf {t > 0: Q(t) greater than or equal to x} be the time of first overflow of a queueing process 1001 over level x (the buffer size) and Z = P(T(X) less than or equal to T). Assuming that {Q(t)) is the reflected version of a Levy process {X(t)} or a Markov additive process, we study a variety of algorithms for estimating z by simulation when the event {tau(X) less than or equal to 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... (More)
Let c(x) = inf {t > 0: Q(t) greater than or equal to x} be the time of first overflow of a queueing process 1001 over level x (the buffer size) and Z = P(T(X) less than or equal to T). Assuming that {Q(t)) is the reflected version of a Levy process {X(t)} or a Markov additive process, we study a variety of algorithms for estimating z by simulation when the event {tau(X) less than or equal to 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=P(tau(x) less than or equal to T), both in the reflected Levy process setting and more generally for regenerative processes in a regime where T is so small that the exponential approximation for T(x) is not a priori valid. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
rare, queueing theory, local time, Levy process, importance sampling, filtered Monte Carlo, buffer overflow, exponential change of measure, event, reflection, regenerative process, saddlepoint
in
Stochastic Processes and their Applications
volume
102
issue
1
pages
1 - 23
publisher
Elsevier
external identifiers
  • wos:000178575400001
  • scopus:0036829392
ISSN
1879-209X
DOI
10.1016/S0304-4149(02)00152-7
language
English
LU publication?
yes
id
b3de0098-715a-4c70-880d-a76dada27a47 (old id 325126)
date added to LUP
2007-08-07 16:12:29
date last changed
2017-08-13 04:19:21
@article{b3de0098-715a-4c70-880d-a76dada27a47,
  abstract     = {Let c(x) = inf {t > 0: Q(t) greater than or equal to x} be the time of first overflow of a queueing process 1001 over level x (the buffer size) and Z = P(T(X) less than or equal to T). Assuming that {Q(t)) is the reflected version of a Levy process {X(t)} or a Markov additive process, we study a variety of algorithms for estimating z by simulation when the event {tau(X) less than or equal to 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=P(tau(x) less than or equal to T), both in the reflected Levy process setting and more generally for regenerative processes in a regime where T is so small that the exponential approximation for T(x) is not a priori valid.},
  author       = {Asmussen, Sören and Fuckerieder, P and Jobmann, M and Schwefel, HP},
  issn         = {1879-209X},
  keyword      = {rare,queueing theory,local time,Levy process,importance sampling,filtered Monte Carlo,buffer overflow,exponential change of measure,event,reflection,regenerative process,saddlepoint},
  language     = {eng},
  number       = {1},
  pages        = {1--23},
  publisher    = {Elsevier},
  series       = {Stochastic Processes and their Applications},
  title        = {Large deviations and fast simulation in the presence of boundaries},
  url          = {http://dx.doi.org/10.1016/S0304-4149(02)00152-7},
  volume       = {102},
  year         = {2002},
}