Asymptotics of first passage times for random walk in an orthant. (English) Zbl 0937.60091

McDonald, D. R.

Ann. Appl. Probab. 9, No. 1, 110-145 (1999).

Author’s abstract: We wish to describe how a chosen node in a network of queues overloads. The overloaded node may also drive other nodes into overload, but the remaining “super” stable nodes are only driven into a new steady state with stochastically larger queues. We model this network of queues as a Markov additive chain with a boundary. The customers at the “super” stable nodes are described by a Markov chain, while the other nodes are described by an additive chain. We use the existence of a harmonic function \(h\) for a Markov additive chain provided by Ney and Nummelin and the asymptotic theory for Markov additive processes to prove asymptotic results on the mean time for a specified additive component to hit a high level \(l\). We give the limiting distribution of the “super” stable nodes at this hitting time. We also give the steady-state distribution of the “super” stable nodes when the specified component equals \(l\). The emphasis here is on sharp asymptotics, not rough asymptotics as in large deviation theory. Moreover, the limiting distributions are for the unscaled process, not for the fluid limit as in large deviation theory.

Reviewer: E.A.van Doorn (Enschede)

MSC:

60K25	Queueing theory (aspects of probability theory)
60K20	Applications of Markov renewal processes (reliability, queueing networks, etc.)

Keywords:

random walk; rare events; change of measure

References:

[1]	Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic. Springer, New York. · Zbl 0679.60013
[2]	Athrey a, K. B., McDonald, D. and Ney, P. (1978). Limit theorems for semi-Markov processes and renewal theory for Markov chains. Ann. Probab. 6 788-797. · Zbl 0397.60052 · doi:10.1214/aop/1176995429
[3]	Baccelli, F. and McDonald, D. (1996). Rare events for stationary processes. Unpublished manuscript. · Zbl 1045.60044
[4]	Beck, B., Dabrowski, A. and McDonald, D. (1997). A unified approach to fast teller queues and ATM. Unpublished manuscript. · Zbl 0952.60096
[5]	Bonneau, M-C. (1996). Accelerated Simulation of a leaky bucket controller. M.Sc. dissertation, Univ. Ottawa.
[6]	Brémaud, P. (1981). Point Processes and Queues, Martingale Dy namics. Springer, New York.
[7]	Doob, J. L. (1959). Discrete potential theory and boundaries. J. Math. Mech. 8 433-458. · Zbl 0101.11503
[8]	Feller, W. (1971). An Introduction to Probability Theory and Its Applications 2. Wiley, New York. · Zbl 0219.60003
[9]	Flatto, L. and Hahn, S. (1985). Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44 1041-1053. JSTOR: · Zbl 0554.90041 · doi:10.1137/0144074
[10]	Foley, R. and McDonald, D. (1997). Join the shortest queue sy stems: stability and exact asy mptotics. Unpublished manuscript.
[11]	Frater, M. R., Lennon, T. M. and Anderson B. D. O. (1991). Optimally efficient estimation of the statistics of rare events in queueing networks. IEEE Trans. Automat. Control 36 1395-1405. · Zbl 0739.60080 · doi:10.1109/9.106155
[12]	Glasserman, G. and Kou, S-G. (1995). Analy sis of an importance sampling estimator for tandem queues. ACM Trans. Modeling Comput. Simul. 5 22-42. · Zbl 0841.62083 · doi:10.1145/203091.203093
[13]	Heidelberger, P. (1995). Fast simulation of rare events in queueing and reliability models. ACM Trans. Modeling Comput. Simul. 5 43-85. · Zbl 0843.62096 · doi:10.1145/203091.203094
[14]	H öglund, T. (1991). The ruin problem for finite Markov chains. Ann. Probab. 19 1298-1310. · Zbl 0744.60083 · doi:10.1214/aop/1176990345
[15]	Huang, C-C. and McDonald, D. (1996). Connection admission control for constant bit rate traffic at a multi-buffer multiplexer using the oldest-cell-first discipline. Unpublished manuscript. Iscoe, I. and McDonald, D. (1994a). Asy mptotics for exit times of Markov jump processes I. Ann. Probab. 22 372-397. Iscoe, I. and McDonald, D. (1994b). Asy mptotics for exit times of Markov jump processes II: application to Jackson networks. Ann. Probab. 22 2168-2182.
[16]	Iscoe, I., McDonald, D. and Xian, K. (1993). Capacity of ATM switches. Ann. Appl. Probab. 3 277-295. · Zbl 0779.60076 · doi:10.1214/aoap/1177005425
[17]	Iscoe, I., McDonald, D. and Xian, K. (1994). Asy mptotics of the exit distribution for Markov jump processes; application to ATM. Canad. J. Math. 46 1238-1262. · Zbl 0814.60069 · doi:10.4153/CJM-1994-070-5
[18]	Keilson, J. (1979). Markov Chain Models-Rarity and Exponentiality. Springer, New York. · Zbl 0411.60068
[19]	Kesten, H. (1974). Renewals theory for functionals of a Markov chain with general state space. Ann. Probab. 2 355-386. · Zbl 0303.60090 · doi:10.1214/aop/1176996654
[20]	Labr eche, N. (1995). Overloading a Jackson network of shared queues. M.Sc. dissertation, Univ. Ottawa.
[21]	Labr eche, N. and McDonald, D. (1995). Overloading a Jackson network of shared queues. Unpublished manuscript.
[22]	McDonald, D. (1996). Overloading parallel servers when arrivals join the shortest queue. Stochastic Networks: Stability and Rare Events. Lecture Notes in Statist. 117 169-196. Springer, New York. · Zbl 0860.60074
[23]	Mey n, P. M. and Frater, M. R. (1993). Recurrence times of buffer overloads in Jackson networks. IEEE Trans. Inform. Theory 39 92-97. · Zbl 0795.68009 · doi:10.1109/18.179346
[24]	Mey n, S. P. and Tweedie R. L. (1993). Markov Chains and Stochastic Stability. Springer, New York. · Zbl 0925.60001
[25]	Ney, P. and Nummelin, E. (1986). Some limit theorems for Markov additive processes. In SemiMarkov Models 3-12. Plenum, New York. Ney, P. and Nummelin, E. (1987a). Markov additive processes I. Eigenvalue properties and limit theorems. Ann. Probab. 15 561-592. Ney, P. and Nummelin, E. (1987b). Markov additive processes II. Large deviations. Ann. Probab. 15 593-609. · Zbl 0625.60027
[26]	Nicola, V. F., Shahabuddin, P., Heidelberger, P. and Gly nn, P. W. (1992). Fast simulation of steady-state availability in non-Markovian highly dependable sy stems. IBM Research Report.
[27]	Orey, S. (1971). Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand Reinhold, New York. · Zbl 0295.60054
[28]	Parekh, S. and Walrand, J. (1989). A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Automat. Control 34 54-66. · Zbl 0661.60110 · doi:10.1109/9.8649
[29]	Shwartz, A. and Weiss, A. (1993). Induced rare events: analysis via large deviations and time reversal. Adv. in Appl. Probab. 25 667-689. JSTOR: · Zbl 0781.60094 · doi:10.2307/1427529
[30]	Sadowsky, J. and Szpankowski, W. (1995). The probability of large queue lengths and waiting times in a heterogeneous multiserver queue I: tight limits. Adv. in Appl. Probab. 27 532-566. JSTOR: · Zbl 0829.60082 · doi:10.2307/1427838
[31]	Wright, P. (1992). Two parallel processors with coupled inputs. Adv. in Appl. Probab. 24 986- 1007. JSTOR: · Zbl 0760.60093 · doi:10.2307/1427722