×

zbMATH — the first resource for mathematics

Exact asymptotics for the stationary distribution of a Markov chain: a production model. (English) Zbl 1188.60046
The authors are interested in estimating the probability of rare events related to the stationary distribution \(\pi \) of Markov chains that typically arise in modeling queueing networks. They develop an approach to deriving the exact asymptotics of \(\pi \) that allows them to analyze situations where the fluid limit of excursions to the (increasingly) rare event is nonlinear. This nonlinear behavior can arise in a pair of stable, \(M/M/1\) queues in tandem. To illustrate the power of the approach, they completely describe the exact asymptotics of \(\pi \) for a production model in all directions and for all stable parameter settings. The production model, described in the paper, has unbounded jumps; at every point in the state space, the boundaries influence the possible transitions. In addition, for certain regions of the parameters, the fluid limits of excursions to the rare events are nonlinear.

MSC:
60K25 Queueing theory (aspects of probability theory)
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
90B22 Queues and service in operations research
60F10 Large deviations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borovkov, A.A., Mogulskii, A.A., Large deviations for Markov chains in the positive quadrant. Usp. Mat. Nauk 56, 3–116 (2001). MR1892559 (2002m:60045)
[2] Breiman, L.: Probability, 1st edn. Addison-Wesley, Reading (1968)
[3] Cinlar, E.: Introduction to Stochastic Processes. Prentice-Hall, New York (1975) · Zbl 0341.60019
[4] Dabrowski, A., Lee, J., McDonald, D.R.: Large deviations of mulitclass M/G/1 queues. Can. J. Stat. 37(3), 327–346 (2009) · Zbl 1180.60076 · doi:10.1002/cjs.10026
[5] Durrett, R.: Probability: Theory and Examples, 3rd edn. Duxbury, N. Scituate (2005) · Zbl 1202.60002
[6] Ethier, S.N., Kurtz, T.G.: Markov Processes. Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics. Wiley, New York (1986), 534 p. · Zbl 0592.60049
[7] Foley, R.D., McDonald, D.R.: Join the shortest queue: stability and exact asymptotics. Ann. Appl. Probab. 11(3), 569–607 (2001). doi: 10.1214/aoap/1015345342 · Zbl 1016.60078
[8] Foley, R.D., McDonald, D.R.: Bridges and networks: Exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005). doi: 10.1214/105051604000000675 · Zbl 1085.60068 · doi:10.1214/105051604000000675
[9] Foley, R.D., McDonald, D.R.: Large deviations of a modified Jackson network: stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005). doi: 10.1214/105051604000000666 · Zbl 1063.60134 · doi:10.1214/105051604000000666
[10] Foley, R.D., McDonald, D.R.: Large deviations and exact asymptotics: a constructive theory (2008, in preparation)
[11] Griffeath, D.: A maximal coupling for Markov chains. Z. Wahrscheinlichkeitstheor. Verw. Geb. 31, 95–106 (1974/75). MR0370771 (51 #6996) · Zbl 0301.60043 · doi:10.1007/BF00539434
[12] Ignatiouk-Robert, I.: Martin boundary of a killed random walk on a half-space. J. Theor. Probab. 21(1), 35–68 (2008). MR2384472 · Zbl 1146.60061 · doi:10.1007/s10959-007-0100-3
[13] Kesten, H.: Renewal theory for functionals of a Markov-chain with general state space. Ann. Probab. 2(3), 355–386 (1974) · Zbl 0303.60090 · doi:10.1214/aop/1176996654
[14] Khanchi, A.: State of a network when one node overloads. Ph.D. Thesis, University of Ottawa (2008).
[15] Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 23(3), 413–438 (2007) · Zbl 1124.60074 · doi:10.1080/15326340701471042
[16] McDonald, D.R.: Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Probab. 9(1), 110–145 (1999). doi: 10.1214/aoap/1029962599 · Zbl 0937.60091 · doi:10.1214/aoap/1029962599
[17] Meyn, S., Tweedie, R.: Markov Chains and Stochastic Stability (1993). citeseer.ist.psu.edu/meyn93crash.html · Zbl 0925.60001
[18] Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis: Queues, Communication, and Computing. Chapman and Hall, London (1995) · Zbl 0871.60021
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.