Large deviations and fast simulation in the presence of boundaries
Sören Asmussen, Pascal Frantz, Manfred Jobmann and HansPeter Schwefel
Centre for Mathematical Sciences
Mathematical Statistics
Lund Institute of Technology,
Lund University,
2000
ISSN 14039338

Abstract:

Let $\tau(x)=\inf\{t>0:\, Q(t)\ge x\}$ be the time of first overflow of
a queueing process $\{Q(t)\}$ over level $x$

(the buffer size) and $z=P(\tau(x)\le 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 $\{\tau(x)\le T\}$ is rare, and analyze 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)\le 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 $\tau(x)$ is not apriori valid.



Key words:

buffer overflow, exponential change of measure, filtered Monte Carlo, importance
sampling, Lévy process, local time, queueing theory, rare event,
reflection, regenerative process, saddlepoint