Abstract
This paper develops an effi cient importance sampling algorithm for comput $ ing steady $ state tail probabilities for customer waiting times in a G/G/2 queue in which the service time requirements are heavy $ tailed random variables. Un $ der appropriate regularity conditions, we prove that our estimator has bounded relative variance whenever the rate at which work arrives to the system is less than 2 (but not equal to one). The argument hinges on the construction of an appropriate Lyapunov function that can be used to bound the second moment of our estimator. The construction followed here uses fluid heuiristics to guess the form of the Lyapunov function, after which tuning constants that define the algorithmic implementation are then chosen in order to force the function to satisfy the required Lyapunov inequality. In addition, the Lyapunov function can be used to obtain upper bounds for large deviation probabilities; thereby not only allowing to study the performance of the algorithm but also provide large deviations estimates. Our approach takes advantage of the regenerative representation for the steady $ state distribution. We therefore also discuss the use of importance sampling, and related effi ciency issues, in conjunction with regenerative steady $ state simulation.
Authors
J Blanchet, P Glynn, J Liu
Publication date
2008
Journal
Department of Statistics, Columbia University
