Leila Setayeshgar
Abstract
The aim of this article is to construct efficient importance sampling schemes for a rare event, namely, the buffer overflow associated with a feed-forward network with discontinuous dynamics. This is done through a piecewise constant change of measure, which is based on a suitably constructed subsolution to an HJB equation. The main task is to change the measure such that the logarithmic asymptotic optimality is achieved. To that end, we find an upper bound on the second moment of the importance sampling estimator that yields optimality. Numerical simulations illustrate the validity of theoretical results.
- Asmussen, S. 2000. Ruin Probabilities. World Scientific, Singapore.Google Scholar
- Blanchet, J. H. and Glynn, P. W. 2008. Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Prob. 18, 1351--1378.Google ScholarCross Ref
- Blanchet, J. H., Glynn, P. W., and Liu, J. 2007. Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue. QUESTA 57, 99--113. Google ScholarDigital Library
- Chung, K. L. 1974. A Course in Probability Theory (2nd ed.). Academic Press, New York.Google Scholar
- De Boer, P. T. 2006. Analysis of state-independent importance sampling measures for the two-node tandem queue. ACM Trans. Modeling Comp. Simulation 16, 225--250. Google ScholarDigital Library
- Dupuis, P. and Ellis, R. 1997. A Weak Convergence Approach to the Theory of Large Deviations. John Wiley & Sons, New York.Google Scholar
- Dupuis, P., Ellis, R., and Weiss, A. 1991. Large deviations for Markov processes with discontinuous statistics, I: General upper bounds. Ann. Probab. 19, 1280--1297.Google ScholarCross Ref
- Dupuis, P., Leder, K., and Wang, H. 2007. Large deviations and importance sampling for a tandem network with slow-down. QUESTA 57, 71--83. Google ScholarDigital Library
- Dupuis, P., Leder, K., and Wang, H. 2009. Importance sampling for weighted serve-the-longest-queue. Math. Oper. Res. 34, 642--660. Google ScholarDigital Library
- Dupuis, P. and Wang, H. 2004. Importance sampling, large deviations, and differential games. Stoch. and Stoch. Reports 76, 481--508.Google ScholarCross Ref
- Dupuis, P. and Wang, H. 2007. Subsolutions of an Isaacs equation and efficient schemes for importance sampling. Math. Oper. Res. 32, 1--35. Google ScholarDigital Library
- Dupuis, P. and Wang, H. 2009. Importance sampling for Jackson networks. QUESTA 62, 113--157. Google ScholarDigital Library
- Gilbarg, D. and Trudinger, N. S. 1983. Elliptic Partial Differential Equations of Second Order (2nd ed.). Springer Verlag, Berlin.Google Scholar
- Glasserman, P. and Wang, Y. 1997. Counter examples in importance sampling for large deviations probabilities. Ann. Appl. Prob. 7, 731--746.Google ScholarCross Ref
- Glynn, P. W. and Iglehart, D. G. 1988. Simulation methods for queues: an overview. QUESTA 3, 221--256. Google ScholarDigital Library
- Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Modeling Comp. Simulation 4, 43--85. Google ScholarDigital Library
- Juneja, S. and Nicola, V. 2005. Efficient simulation of buffer overflow probabilities in Jackson networks with feedback. ACM Trans. Modeling Comp. Simulation 15, 281--315. Google ScholarDigital Library
- Miretskiy, D. I., Scheinhardt, W. R. W., and Mandjes, M. R. H. 2007. Efficient simulation of a tandem queue with server slowdown. Simulation 83, 751--767. Google ScholarDigital Library
- Parekh, S. and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Control 34, 54--66.Google ScholarCross Ref
- Protter, P. 1995. Stochastic Integration and Differential Equations. Springer, New York.Google Scholar
- Sadowsky, J. S. 1996. On Monte Carlo estimation of large deviations probabilities. Ann. Appl. Prob. 6, 399--422.Google ScholarCross Ref
- Setayeshgar, L. and Wang, H. 2011. Large deviations for a feed-forward network. Adv. Appl. Prob. 43, 545--571.Google ScholarCross Ref
- Sezer, A. D. 2009. Importance sampling for a Markov modulated queuing network. Stoch. Proc. Appl. 119, 491--517.Google ScholarCross Ref
- Shahsbuddin, P. 1994. Importance sampling for the simulation of highly reliable Markovian systems. Manage. Sci. 40, 333--352. Google ScholarDigital Library
- Siegmund, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673--684.Google ScholarCross Ref
Index Terms
- Efficient importance sampling schemes for a feed-forward network
Recommendations
Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling
It was established in Dupuis and Wang [Dupuis, P., H. Wang. 2004. Importance sampling, large deviations, and differential games. Stoch. Stoch. Rep.76 481--508, Dupuis, P., H. Wang. 2005. Dynamic importance sampling for uniformly recurrent Markov chains. ...
Importance sampling for Jackson networks
Rare event simulation in the context of queueing networks has been an active area of research for more than two decades. A commonly used technique to increase the efficiency of Monte Carlo simulation is importance sampling. However, there are few ...
Importance sampling: a review
AbstractWe provide a short overview of importance sampling—a popular sampling tool used for Monte Carlo computing. We discuss its mathematical foundation and properties that determine its accuracy in Monte Carlo approximations. We review the fundamental ...
Comments