State-dependent importance sampling for a Jackson tandem network

D.I. Miretskiy, Willem R.W. Scheinhardt, M.R.H. Mandjes

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)


This article considers importance sampling as a tool for rare-event simulation. The focus is on estimating the probability of overflow in the downstream queue of a Jacksonian two-node tandem queue; it is known that in this setting “traditional‿ state-independent importance-sampling distributions perform poorly. We therefore concentrate on developing a state-dependent change of measure, that we prove to be asymptotically efficient. More specific contributions are the following. (i) We concentrate on the probability of the second queue exceeding a certain predefined threshold before the system empties. Importantly, we identify an asymptotically efficient importance-sampling istribution for any initial state of the system. (ii) The choice of the importance-sampling distribution is backed up by appealing heuristics that are rooted in large-deviations theory. (iii) The method for proving asymptotic efficiency relies on probabilistic arguments only. The article is concluded by simulation experiments that show a considerable speedup.
Original languageUndefined
Pages (from-to)15
Number of pages26
JournalACM transactions on modeling and computer simulation
Issue number3
Publication statusPublished - 2010


  • EWI-19003
  • IR-75061
  • METIS-276724

Cite this