Polynomial Time Algorithms for Estimation of Rare Events in Queueing Models

This paper presents a framework for analyzing time complexity of rare events estimators for queueing models. In particular it deals with polynomial and exponential time switching regenerative (SR) estimators for the steady-state probabilities of excessive backlog in the GI=GI=1 queue, and some of its extensions. The SR estimators are based on large deviation theory and exponential change of measure, which is parametrized by a scalar t. We show how to find the optimal value w of the parameter t, which leads to the optimal exponential change of measure (OECM), and we find conditions under which the OECM generates polynomial time estimators. We, finally, investigate the "robustness" of the proposed SR estimators, in the sense that we find how much one can perturb the optimal value w in the OECM such that the SR estimator still leads to dramatic variance reduction and still is useful in practice. Our extensive numerical results suggest that if the optimal parameter value w is perturbed up to 20%, we only lose 2--3 orders of magnitude of variance reduction compared to the orders of tenth under the optimal value w.