Importance sampling for a Markov modulated queuing network. (English) Zbl 1157.60345
Summary: Importance sampling (IS) is a variance reduction method for simulating rare events. A recent paper by P. Dupuis, H. Wang and A. D. Sezer [Ann. Appl. Probab. 17, No. 4, 1306–1346 (2007; Zbl 1144.60022)] exploits connections between IS and stochastic games and optimal control problems to show how to design and analyze simple and efficient IS algorithms for various overflow events of tandem Jackson Networks. The present paper carries out a program parallel to the paper by Dupuis et al. for a two node tandem network whose arrival and service rates are modulated by an exogenous finite state Markov process. The overflow event we study is the following: the number of customers in the system reaches \(n\) without the system ever becoming empty, given that initially the system is empty.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 49N90 | Applications of optimal control and differential games |
| 60F10 | Large deviations |
| 65C05 | Monte Carlo methods |
| 91A15 | Stochastic games, stochastic differential games |
| 91A23 | Differential games (aspects of game theory) |
Keywords:
dynamic importance sampling; rare event simulation; tandem queues; queuing networks; Markov modulated; regime switch; overflow probability; large deviations; Isaacs equation; optimal controlCitations:
Zbl 1144.60022Software:
OctaveReferences:
| [1] | Dupuis, Paul; Ellis, Richard S., A Weak Convergence Approach to the Theory of Large Deviations (1997), John Wiley & Sons: John Wiley & Sons New York · Zbl 0904.60001 |
| [2] | Dupuis, Paul; Ellis, Richard S.; Weiss, Alan, Large deviations for Markov processes with discontinuous statistics. I. General upper bounds, The Annals of Probability, 19, 3, 1280-1297 (1991) · Zbl 0735.60027 |
| [3] | Dupuis, Paul; Kushner, Harold, Stochastic approximation and large deviations: upper bounds and w.p.1 convergence, SIAM Journal on Control and Optimization, 27, 1108-1135 (1989) · Zbl 0679.60041 |
| [4] | Dupuis, Paul; Wang, Hui, Importance sampling, large deviations and differential games, Stochastics and Stochastic Reports, 76(, 6, 481-508 (2004) · Zbl 1076.65003 |
| [5] | Dupuis, Paul; Wang, Hui, Adaptive importance sampling for uniformly recurrent markov chains, Annals of Applied Probability, 15, 1, 1-38 (2005) · Zbl 1068.60036 |
| [6] | Paul Dupuis, Hui Wang, Subsolutions of an isaacs equation and efficient schemes for importance sampling: Convergence analysis, 2005, Preprint available at: http://www.dam.brown.edu/people/huiwang; Paul Dupuis, Hui Wang, Subsolutions of an isaacs equation and efficient schemes for importance sampling: Convergence analysis, 2005, Preprint available at: http://www.dam.brown.edu/people/huiwang · Zbl 1341.62042 |
| [7] | Paul Dupuis, Hui Wang, Subsolutions of an isaacs equation and efficient schemes for importance sampling: Examples and numerics, 2005, preprint available at: http://www.dam.brown.edu/lcds/publications; Paul Dupuis, Hui Wang, Subsolutions of an isaacs equation and efficient schemes for importance sampling: Examples and numerics, 2005, preprint available at: http://www.dam.brown.edu/lcds/publications · Zbl 1341.62042 |
| [8] | Durrett, Richard, Probability: Theory and Examples (1996), Duxbury Press: Duxbury Press Belmont, CA · Zbl 0709.60002 |
| [9] | Eaton, John W., GNU Octave Manual (2002), Network Theory Limited |
| [10] | Fleming, Wendell H.; Rishel, Raymond W., (Deterministic and Stochastic Optimal Control. Deterministic and Stochastic Optimal Control, Applications of Mathematics, vol. 1 (1975), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0323.49001 |
| [11] | Freidlin, Mark I.; Wentzell, Alexander D., Random Perturbation of Dynamical Systems (1998), Springer-Verlag: Springer-Verlag Telos · Zbl 0922.60006 |
| [12] | Glasserman, Paul; Kou, Shing-Gang, Analysis of an importance sampling estimator for tandem queues, ACM Transactions on Modeling and Computer Simulation, 5, 22-42 (1995) · Zbl 0841.62083 |
| [13] | Lions, Pierre-Louis, Neumann type boundary conditions for Hamilton-Jacobi equations, Duke Mathematics Journal, 52, 793-820 (1985) · Zbl 0599.35025 |
| [14] | Ali Devin Sezer, Asymptotically optimal importance sampling for jackson networks with a tree topology, Preprint available at: http://www.dam.brown.edu/people/sezer; Ali Devin Sezer, Asymptotically optimal importance sampling for jackson networks with a tree topology, Preprint available at: http://www.dam.brown.edu/people/sezer · Zbl 1182.90027 |
| [15] | Ali Devin Sezer, A large deviation upper bound for a buffer overflow event of a markov modulated queuing network. Preprint available at: http://www.dam.brown.edu/people/sezer; Ali Devin Sezer, A large deviation upper bound for a buffer overflow event of a markov modulated queuing network. Preprint available at: http://www.dam.brown.edu/people/sezer · Zbl 1157.60345 |
| [16] | Ali Devin Sezer, Representation results for largest eigenvalues of matrices with positive entries, Preprint available at: http://www.dam.brown.edu/people/sezer; Ali Devin Sezer, Representation results for largest eigenvalues of matrices with positive entries, Preprint available at: http://www.dam.brown.edu/people/sezer · Zbl 1182.90027 |
| [17] | Ali Devin Sezer, Dynamic Importance Sampling for Queueing Networks, Ph.D. Thesis, Brown University Division of Applied Mathematics, 2005. Preprint available at: http://www.dam.brown.edu/people/sezer; Ali Devin Sezer, Dynamic Importance Sampling for Queueing Networks, Ph.D. Thesis, Brown University Division of Applied Mathematics, 2005. Preprint available at: http://www.dam.brown.edu/people/sezer · Zbl 1144.60022 |
| [18] | Dupuis, Paul; Sezer, Ali Devin; Wang, Hui, Dynamic importance sampling for queueing networks, Annals of Applied Probability, 17, 4, 1306-1346 (2007) · Zbl 1144.60022 |
| [19] | Shiryaev, Albert Nikolaevich, Probability (1995), Springer · Zbl 0835.60002 |
| [20] | Siegmund, David, Importance sampling in the monte carlo study of sequential tests, The Annals of Statistics, 4, 673-684 (1976) · Zbl 0353.62044 |
| [21] | Walrand, Jean; Parekh, S., A quick simulation method for excessive backlogs in networks of queues, IEEE Transactions on Automatic Control, 34, 54-66 (1989) · Zbl 0661.60110 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
