Efficient Importance Sampling Heuristics for the Simulation of Population Overflow in Feed-Forward Queueing Networks

In this paper we propose a state-dependent importance sampling heuristic to estimate the probability of population overflow in feed-forward networks. This heuristic attempts to approximate the “optimal��? state-dependent change of measure without the need for difficult analysis or costly optimization involved in other recently proposed adaptive importance sampling algorithms. Preliminary simulation experiments with a 4-node feed-forward network yield asymptotically efficient estimates, with relative error increasing at most linearly in the overflow level, where state-independent importance sampling is demonstrably ineffective