Analysis of an importance sampling estimator for tandem queues
- 1 January 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 5 (1), 22-42
- https://doi.org/10.1145/203091.203093
Abstract
We analyze the performance of an importance sampling estimator for a rare-event probability in tandem Jackson networks. The rare event we consider corresponds to the network population reaching K before returning to ø, starting from ø, with K large. The estimator we study is based on interchanging the arrival rate and the smallest service rate and is therefore a generalization of the asymptotically optimal estimator for an M/M/1 queue. We examine its asymptotic performance for large K , showing that in certain parameter regions the estimator has an asymptotic efficiency property, but that in other regions it does not. The setting we consider is perhaps the simplest case of a rare-event simulation problem in which boundaries on the state space play a significant role.Keywords
This publication has 14 references indexed in Scilit:
- Correctness within a constant of an optimal buffer allocation rule of thumbIEEE Transactions on Information Theory, 1994
- Quick simulation of ATM buffers with on-off multiclass Markov fluid sourcesACM Transactions on Modeling and Computer Simulation, 1993
- Optimally efficient estimation of the statistics of rare events in queueing networksIEEE Transactions on Automatic Control, 1991
- Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queueIEEE Transactions on Automatic Control, 1991
- A Viscosity Solution Approach to the Asymptotic Analysis of Queueing SystemsThe Annals of Probability, 1990
- The optimal buffer allocation problemIEEE Transactions on Information Theory, 1989
- Moments for first-passage and last-exit times, the minimum, and related quantities for random walks with positive driftAdvances in Applied Probability, 1986
- Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queueAdvances in Applied Probability, 1982
- The interchangeability of ·/M/1 queues in seriesJournal of Applied Probability, 1979
- Importance Sampling in the Monte Carlo Study of Sequential TestsThe Annals of Statistics, 1976