Large deviations and fast simulation in the presence of boundaries

Sören Asmussen, Pascal Frantz, Manfred Jobmann and Hans-Peter Schwefel

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, saddle-point