Previous work on state-dependent adaptive importance sampling techniques for the simulation of rare events in Markovian queueing models used either no smoothing or a parametric smoothing technique, which was known to be non-optimal. In this paper, we introduce the use of kernel smoothing in this conteXt. We derive eXpressions for the smoothed transition probabilities, compare several variations of the technique, and eXplore the choice of kernel width. We provide some eXamples, demonstrating that the technique significantly improves convergence and estimator variance.
Parekh, S. and J. Walrand.1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Transactions on Automatic Control34, 54-66.
2.
Sadowsky, J.S.1991. Large deviations theory and efficient simulation of excessive backlogs in a gi/gi/m queue. IEEE Transactions on Automatic Control36, 1383-1394.
3.
Glasserman, P. and S.-G. Kou .1995. Analysis of an importance sampling estimator for tandem queues. ACM Transactions on Modeling and Computer Simulation5(1), 22-42.
4.
de Boer, P.T.2006. Analysis of state-independent IS measures for the two-node tandem queue. ACM Transactions on Modeling and Computer Simulation16, 225-250.
5.
Nicola, V.F. and T.S. Zaburnenko .2005. Importance sampling simulation of population overflow in two-node tandem networks. In 2nd International Conference on the Quantitative Evaluation of Systems, QEST'05 , pp. 220-229.
6.
Kroese, D.P. and V.F. Nicola.2002. Efficient simulation of a tandem jackson network. ACM Transactions on Modeling and Computer Simulation12(2), 119-141.
7.
Dupuis, P. , A.D. Sezer, and H. Wang.2007. Dynamic importance sampling for queueing networks. Ann. Appl. Probab., 17(4), 1306-1346.
8.
Devetsikiotis, M. and J.K. Townsend.1993. Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks. IEEE/ACM Transactions on Networking1, 293-305.
9.
de Boer, P.T. and V.F. Nicola.2002. Adaptive state-dependent importance sampling simulation of markovian queueing networks. European Transactions on Telecommunications13(4), 303-315.
10.
Ahamed, T.P.I. , V.S. Borkar, and S. Juneja.2006. Adaptive importance sampling technique for Markov chains using stochastic approximation. Operations Research54(3), 489-504. ISSN 0030-364X.
11.
de Boer, P.T.2000. Analysis and efficient simulation of queueing models of telecommunication systems. Ph.D. thesis, University of Twente.
12.
Heidelberger, P.1995. Fast simulation of rare events in queueing and reliability models. ACM Transactions on Modeling and Computer Simulation5, 43-85.
13.
de Boer, P.T., D.P. Kroese, S. Mannor, and R.Y. Rubinstein.2005. A tutorial on the cross-entropy method. Annals of Operations Research134(1), 19-67.
14.
Woudt, E.2006. Optimization of simulation of overflows in Markovian queueing models. MSc thesis, University of Twente.
15.
Wand, M. and M. Jones.1995. Kernel smoothing, volume 60 of Monographs on statistics and applied probability. London: Chapman & Hall.
16.
Yang, L. and R. Tschernig.1999. Multivariate bandwidth selection for local linear regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology)61(4), 793-815.
17.
Frater, M.R. , T.M. Lennon, and B.D. Anderson.1991. Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Transactions on Automatic Control36, 1395- 1405.
