Abstract
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.
Original language | English |
---|---|
Journal | Stochastic Processes and Their Applications |
Volume | 102 |
Issue number | 1 |
Pages (from-to) | 1-23 |
Number of pages | 23 |
ISSN | 0304-4149 |
DOIs | |
Publication status | Published - 1 Nov 2002 |
Externally published | Yes |
Keywords
- Buffer overflow
- Exponential change of measure
- Filtered Monte Carlo
- Importance sampling Lévy process
- Local time
- Queueing theory
- Rare event
- Reflection
- Regenerative process
- Saddlepoint