Analysis of a state-independent change of measure for the G|G|1 tandem queue

In (Parekh and Walrand, 1989) a method is introduced to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level N in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state-independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown in (Sadowsky, 1991) that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions.In this work we study the state-independent change of measure of the G|G|1 tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the G|G|1 tandem queue had been obtained previously. Looking at the results of the M|M|1 tandem queue, it is expected that this state-independent change of measure is the only state-independent change of measure for the G|G|1 tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node G|G|1 tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.