Blanchet, J., Glynn, P., & Liu, J. C. (2007). Eo cient Rare Event Simulation for Heavy $ tailed Multiserver Queues.
Abstract
This paper develops an eo 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 …
Authors
J Blanchet, P Glynn, JC Liu
Publication date
2007/3
