Optimal Sampling of Overflow Paths in Jackson Networks.

Summary:

It takes Ω(N) steps for the total population of a Jackson network to reach level N within a busy period. And, it takes exponentially many (in N) busy periods to observe this phenomenon. This paper describes how to simulate paths conditional on overflow in (optimal) O(N) running time. As a corollary the algorithms yield strongly efficient estimators for overflow probabilities. This is the first paper that obtains strongly efficient estimators for these types of networks. It is very interesting to note that conditional limit theorems of the network given overflow are valid only for extremely small values of the probability associated to the rare-event of interest. So the conditional sampling algorithm has, in my view, substantial value. We are working on extending these ideas to more general classes of networks!

Bibtex:

@Article {Blanchet09,

author = {J. Blanchet},

title = {Optimal Sampling of Overflow Paths in Jackson Networks},

journal = {forthcoming},

year = {2009},

OPTkey = {},

volume = {},

OPTnumber = {},

pages = {}

}