Optimal importance sampling for Markovian systems with applications to tandem queues Original Research Article

Importance sampling is a change-of-measure technique for speeding up the simulation of rare events in stochastic systems. In this paper we establish a number of properties characterizing optimal importance sampling measures for Markovian systems. We use these properties to develop a new method for computing the optimal measure and give specific results for a tandem queueing system. Optimal measures, though as diffcult to compute as the rare event probability itself, give useful insight into the characteristics of importance sampling measures. Our approach has no immediate computational advantage over other methods, but it suggests a number of heuristic approximations which may lead to computationally attractive methods.