Simulating Tail Probabilities in GI/GI.1 Queues and Insurance Risk Processes with Subexponentail Distributions

This paper deals with estimating small tail probabilities of thesteady-state waiting time in a GI/GI/1 queue withheavy-tailed (subexponential) service times. The problem ofestimating infinite horizon ruin probabilities in insurancerisk processes with heavy-tailed claims can be transformed into thesame framework. It is well-known that naivesimulation is ineffective for estimating small probabilities andspecial fast simulation techniques like importancesampling, multilevel splitting, etc., have to be used. Though thereexists a vast amount of literature on the rare eventsimulation of queuing systems and networks with light-taileddistributions, previous fast simulation techniques forqueues with subexponential service times have been confined to theM/GI/1 queue. The general approach is to use thePollaczek-Khintchine transformation to convert the problem into thatof estimating the tail distribution of a geometricsum of independent subexponential random variables. However, no suchuseful transformation exists when one goesfrom Poisson arrivals to general interarrival-time distributions. Wedescribe and evaluate an approach that is based ondirectly simulating the random walk associated with the waiting-timeprocess of the GI/GI/1 queue, using a change ofmeasure called delayed subexponential twisting -an importancesampling idea recently developed and found useful inthe context of M/GI/1 heavy-tailed simulations.