Large deviations and fast simulation in the presence of boundaries

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Probability Theory and Statistics (hsv//eng)

Nyckelord

rare

queueing theory

local time

Levy process

importance sampling

filtered Monte Carlo

buffer overflow

exponential change of measure

event

reflection

regenerative process

saddlepoint

Publikations- och innehållstyp

art (ämneskategori)

ref (ämneskategori)