×

zbMATH — the first resource for mathematics

Analysis of a splitting estimator for rare event probabilities in Jackson networks. (English) Zbl 1291.60150
Summary: We consider a standard splitting algorithm for the rare-event simulation of overflow probabilities in any subset of stations in a Jackson network at level \(n\), starting at a fixed initial position. It was shown in [T. Dean and P. Dupuis, Stochastic Processes Appl. 119, No. 2, 562–587 (2009; Zbl 1157.60019)] that a subsolution to the Isaacs equation guarantees that a subexponential number of function evaluations (in \(n\)) suffices to estimate such overflow probabilities within a given relative accuracy. Our analysis here shows that in fact \(O(n^{2\beta_V+1})\) function evaluations suffice to achieve a given relative precision, where \(\beta_V\) is the number of bottleneck stations in the subset of stations under consideration in the network. This is the first rigorous analysis that favorably compares splitting against directly computing the overflow probability of interest, which can be evaluated by solving a linear system of equations with \(O(n^d)\) variables.

MSC:
60J22 Computational methods in Markov chains
Software:
RESTART
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] V. Anantharam, P. Heidelberger, and P. Tsoucas. Analysis of rare events in continuous time marked chains via time reversal and fluid approximation. IBM Research Report, REC 16280 , 1990.
[2] P. Arbenz and W. Gander. A survey of direct parallel algorithms for banded linear systems. Technical Report 221, Department Informatik,ETH Zurich, 1994. · Zbl 0900.65070
[3] S. Asmussen and P. Glynn. Stochastic Simulation: Algorithms and Analysis . Springer-Verlag, New York, NY, USA, 2008. · Zbl 1126.65001
[4] J. Blanchet. Optimal sampling of overflow paths in Jackson networks. To Appear in Math. of O.R. , 2011. · Zbl 1291.65010
[5] J. Blanchet and P. Glynn. Efficient rare-event simulation for the maximum of a heavy-tailed random walk. Ann. of Appl. Probab. , 18:1351-1378, 2008. · Zbl 1147.60315
[6] J. Blanchet, K. Leder, and P. Glynn. Lyapunov functions and subsolutions for rare event simulation. Submitted , 2011.
[7] J. Blanchet and M. Mandjes. Rare event simulation for queues. In G. Rubino and B. Tuffin, editors, Rare Event Simulation Using Monte Carlo Methods , pages 87-124. Wiley, West Sussex, United Kingdom, 2009. Chapter 5. · Zbl 1175.65013
[8] T. Dean and P. Dupuis. Splitting for rare event simulation: A large deviation approach to design and analysis. Stochastic Processes and Its Applications , (119):562-587. · Zbl 1157.60019
[9] P. Dupuis and R. S. Ellis. The large deviation principle for a general class of queueing systems I. Trans. of the American Mathematical Society , 347:2689-2751, 1995. · Zbl 0869.60022
[10] P. Dupuis, A. Sezer, and H. Wang. Dynamic importance sampling for queueing networks. Ann. Appl. Probab. , 17:1306-1346, 2007. · Zbl 1144.60022
[11] P. Dupuis and H. Wang. Importance sampling, large deviations, and differential games. Stoch. and Stoch. Reports , 76:481-508, 2004. · Zbl 1076.65003
[12] P. Dupuis and H. Wang. Importance sampling for Jackson networks. Preprint , 2008. · Zbl 1166.60329
[13] P. Glasserman, P. Heidelberger, P. Shahabuddin, and T. Zajic. Multilevel splitting for estimating rare event probabilities, 1999. · Zbl 0985.65006
[14] P. Glasserman and S. Kou. Analysis of an importance sampling estimator for tandem queues. ACM TOMACS , 5:22-42, 1995. · Zbl 0841.62083
[15] I. Ignatiouk-Robert. Large deviations of Jackson networks. Annals of Applied Probability , 10:962-1001, 2000. · Zbl 1073.60510
[16] S. Juneja and V. Nicola. Efficient simulation of buffer overflow probabilities in Jackson networks with feedback. ACM Trans. Model. Comput. Simul. , 15(4):281-315, 2005. · Zbl 1390.90224
[17] S. Juneja and P. Shahabuddin. Rare event simulation techniques: An introduction and recent advances. In S. G. Henderson and B. L. Nelson, editors, Simulation , Handbooks in Operations Research and Management Science, pages 291-350. Elsevier, Amsterdam, The Netherlands, 2006.
[18] D. Kroese and V. Nicola. Efficient simulation of a tandem Jackson network. ACM Trans. Model. Comput. Simul. , 12:119-141, 2002. · Zbl 1390.90231
[19] K. Majewski and K. Ramanan. How large queues build up in a Jackson network. To Appear in Math. of O.R. , 2008.
[20] M.Villen-Altamirano and J. Villen-Altamirano. Restart: A method for accelerating rare even simulations. In J.W. Colhen and C.D. Pack, editors, Proceedings of the 13th International Teletraffic Congress. In Queueing, performance and control in ATM , pages 71-76. Elsevier Science Publishers, 1993. · Zbl 0729.90894
[21] V. Nicola and T. Zaburnenko. Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks. ACM Trans. Model. Comput. Simul. , 17(2), 2007. · Zbl 1390.90249
[22] S. Parekh and J. Walrand. Quick simulation of rare events in networks. IEEE Trans. Automat. Contr. , 34:54-66, 1989. · Zbl 0661.60110
[23] P. Robert. Stochastic Networks and Queues . Springer-Verlag, Berlin, 2003. · Zbl 1038.60091
[24] M. Villén-Altamirano and J. Villén-Altamirano. Restart: a straightforward method for fast simulation of rare events. In Winter Simulation Conference , pages 282-289, 1994.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.