Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 1 (2011) open journal systems 


Analysis of a splitting estimator for rare event probabilities in Jackson networks

Jose Blanchet, Columbia University
Kevin Leder, University of Minnesota
Yixi Shi, Columbia University


Abstract
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 [8] 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.

Creative Common LOGO

Full Text: PDF


Blanchet, Jose, Leder, Kevin, Shi, Yixi, Analysis of a splitting estimator for rare event probabilities in Jackson networks, Stochastic Systems, 1, (2011), 306-339 (electronic). DOI: 10.1214/11-SSY026.

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.

[3]   S. Asmussen and P. Glynn. Stochastic Simulation: Algorithms and Analysis. Springer-Verlag, New York, NY, USA, 2008. MR2331321

[4]   J. Blanchet. Optimal sampling of overflow paths in Jackson networks. To Appear in Math. of O.R., 2011.

[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. MR2434174

[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. MR2730763

[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. MR2494004

[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. MR1290716

[10]   P. Dupuis, A. Sezer, and H. Wang. Dynamic importance sampling for queueing networks. Ann. Appl. Probab., 17:1306–1346, 2007. MR2344308

[11]   P. Dupuis and H. Wang. Importance sampling, large deviations, and differential games. Stoch. and Stoch. Reports, 76:481–508, 2004. MR2100018

[12]   P. Dupuis and H. Wang. Importance sampling for Jackson networks. Preprint, 2008.

[13]   P. Glasserman, P. Heidelberger, P. Shahabuddin, and T. Zajic. Multilevel splitting for estimating rare event probabilities, 1999. MR1710951

[14]   P. Glasserman and S. Kou. Analysis of an importance sampling estimator for tandem queues. ACM TOMACS, 5:22–42, 1995.

[15]   I. Ignatiouk-Robert. Large deviations of Jackson networks. Annals of Applied Probability, 10:962–1001, 2000. MR1789985

[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.

[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.

[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.

[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.

[22]   S. Parekh and J. Walrand. Quick simulation of rare events in networks. IEEE Trans. Automat. Contr., 34:54–66, 1989. MR0970932

[23]   P. Robert. Stochastic Networks and Queues. Springer-Verlag, Berlin, 2003. MR1996883

[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.




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238