Abstract
We derive rough and exact asymptotic expressions for the stationary distribution π of a Markov chain arising in a queueing/production context. The approach we develop can also handle “cascades,” which are situations where the fluid limit of the large deviation path from the origin to the increasingly rare event is nonlinear. Our approach considers a process that starts at the rare event. In our production example, we can have two sequences of states that asymptotically lie on the same line, yet π has different asymptotics on the two sequences.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
Breiman, L.: Probability, 1st edn. Addison-Wesley, Reading (1968)
Cinlar, E.: Introduction to Stochastic Processes. Prentice-Hall, New York (1975)
Dabrowski, A., Lee, J., McDonald, D.R.: Large deviations of mulitclass M/G/1 queues. Can. J. Stat. 37(3), 327–346 (2009)
Durrett, R.: Probability: Theory and Examples, 3rd edn. Duxbury, N. Scituate (2005)
Ethier, S.N., Kurtz, T.G.: Markov Processes. Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics. Wiley, New York (1986), 534 p.
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
Foley, R.D., McDonald, D.R.: Bridges and networks: Exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005). doi:10.1214/105051604000000675
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
Foley, R.D., McDonald, D.R.: Large deviations and exact asymptotics: a constructive theory (2008, in preparation)
Griffeath, D.: A maximal coupling for Markov chains. Z. Wahrscheinlichkeitstheor. Verw. Geb. 31, 95–106 (1974/75). MR0370771 (51 #6996)
Ignatiouk-Robert, I.: Martin boundary of a killed random walk on a half-space. J. Theor. Probab. 21(1), 35–68 (2008). MR2384472
Kesten, H.: Renewal theory for functionals of a Markov-chain with general state space. Ann. Probab. 2(3), 355–386 (1974)
Khanchi, A.: State of a network when one node overloads. Ph.D. Thesis, University of Ottawa (2008).
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)
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
Meyn, S., Tweedie, R.: Markov Chains and Stochastic Stability (1993). citeseer.ist.psu.edu/meyn93crash.html
Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis: Queues, Communication, and Computing. Chapman and Hall, London (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of R.D. Foley supported in part by NSF Grant CMMI-0856489.
Research of D.R. McDonald supported in part by NSERC Grant A4551.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Adan, I., Foley, R.D. & McDonald, D.R. Exact asymptotics for the stationary distribution of a Markov chain: a production model. Queueing Syst 62, 311–344 (2009). https://doi.org/10.1007/s11134-009-9140-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-009-9140-y
Keywords
- Rare events
- Large deviations
- Exact asymptotics
- Change of measure
- h transform
- Time reversal
- Markov additive process
- Markov chain
- R-transient