Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that the authors answer in this paper for the waiting time moments (of arbitrary order) of the M/G/1 queue by using the queueing analysis technique developed by Shalmon. They present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for the M/G/1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arrivals.