Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-30T18:11:27.107Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing Stationary Expectations in Level-Dependent QBD Processes

Part of: Markov processes

Published online by Cambridge University Press:  30 January 2018

Hendrik Baumann  and
Werner Sandmann
Hendrik Baumann*
Affiliation:
Clausthal University of Technology
Werner Sandmann*
Affiliation:
Clausthal University of Technology
*
∗ Postal address: Department of Applied Stochastics and Operations Research, Clausthal University of Technology, Erzstr. 1, D-38678, Clausthal-Zellerfeld, Germany.
∗ Postal address: Department of Applied Stochastics and Operations Research, Clausthal University of Technology, Erzstr. 1, D-38678, Clausthal-Zellerfeld, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Stationary expectations corresponding to long-run averages of additive functionals on level-dependent quasi-birth-and-death processes are considered. Special cases include long-run average costs or rewards, moments and cumulants of steady-state queueing network performance measures, and many others. We provide a matrix-analytic scheme for numerically computing such stationary expectations without explicitly computing the stationary distribution of the process, which yields an algorithm that is as quick as its counterparts for stationary distributions but requires far less computer storage. Specific problems arising in the case of infinite state spaces are discussed and the application of the algorithm is demonstrated by a queueing network example.

Keywords

Level-dependent quasi-birth-and-death processmatrix-analytic computationlong-run average additive functionalstationary expectationmemory-efficient algorithm

MSC classification

Primary: 60J22: Computational methods in Markov chains
Secondary: 60J27: Continuous-time Markov processes on discrete state spaces 60J28: Applications of continuous-time Markov processes on discrete state spaces
Type
Research Article
Information
Journal of Applied Probability , Volume 50 , Issue 1 , March 2013 , pp. 151 - 165
Copyright
Copyright © Applied Probability Trust 2013 

References

Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
Baumann, H. and Sandmann, W. (2010). Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1, 1561–1569.Google Scholar
Baumann, H. and Sandmann, W. (2012). Steady state analysis of level dependent quasi-birth-and-death processes with catastrophes. Comput. Operat. Res. 39, 413–423.CrossRefGoogle Scholar
Bright, L. and Taylor, P. G. (1995). Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Commun. Statist. Stoch. Models 11, 497–525.Google Scholar
Dayar, T., Sandmann, W., Spieler, D. and Wolf, V. (2011). Infinite level-dependent QBD processes and matrix-analytic solutions for stochastic chemical kinetics. Adv. Appl. Prob. 43, 1005–1026.CrossRefGoogle Scholar
Gaver, D. P., Jacobs, P. A. and Latouche, G. (1984). Finite birth-and-death models in randomly changing environments. Adv. Appl. Prob. 16, 715–731.Google Scholar
Glynn, P. W. and Zeevi, A. (2008). Bounding stationary expectations of Markov processes. In Markov Processes and Related Topics: A Festschrift for Thomas G. Kurtz (Inst. Math. Statist. Collect. 4), Institute of Mathematical Statistics, Beachwood, OH, pp. 195–214.CrossRefGoogle Scholar
Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore, MD.Google Scholar
Hanschke, T. (1999). A matrix continued fraction algorithm for the multiserver repeated order queue. Math. Comput. Modelling 30, 159–170.Google Scholar
Knuth, D. E. (1998). The Art of Computer Programming, Vol. 2, 3rd edn. Addison-Wesley.Google Scholar
Kumar, S. and Kumar, P. R. (1994). Performance bounds for queueing networks and scheduling policies. {IEEE Trans. Automatic Control} 39, 1600–1611.Google Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia, PA.Google Scholar
Morrison, J. R. and Kumar, P. R. (2008). Computational performance bounds for Markov chains with applications. {IEEE Trans. Automatic Control} 53, 1306–1311.CrossRefGoogle Scholar
Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD.Google Scholar
Serfozo, R. (2009). Basics of Applied Stochastic Processes. Springer, Berlin.CrossRefGoogle Scholar
Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press.Google Scholar
Thorne, J. (1997). An investigation of algorithms for calculating the fundamental matrices in level dependent quasi birth death processes. Honours thesis, The University of Adelaide.Google Scholar