Computing stationary expectations in level-dependent QBD processes. (English) Zbl 1273.60089

In this paper the authors discuss a novel method to numerically compute the expectations of additive functionals with respect to the stationary distribution of a quasi-birth-and-death process, i.e., Markov chains with generator which is a block-diagonal matrix. The algorithm is applicable to finite-state space chains but specific issues arising in using the method for truncated infinite state space chains are also discussed.
The presented method is based on matrix-analytic techniques and avoids the explicit computation of the stationary distribution when evaluating the expectation of functionals. In this way the algorithm requires far less computer storage than algorithms calculating the stationary distribution directly but does not incur any losses in speed.
A numerical example of a queuing network is used to illustrate the performance of the method.


60J22 Computational methods in Markov chains
60J27 Continuous-time Markov processes on discrete state spaces
60J28 Applications of continuous-time Markov processes on discrete state spaces
Full Text: DOI Euclid


[1] Asmussen, S. (2003). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 1029.60001
[2] Baumann, H. and Sandmann, W. (2010). Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1, 1561-1569.
[3] 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. · Zbl 1251.90086
[4] 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. · Zbl 0837.60081 · doi:10.1080/15326349508807357
[5] 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. · Zbl 1233.60042 · doi:10.1239/aap/1324045696
[6] 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. · Zbl 0554.60079 · doi:10.2307/1427338
[7] 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. · Zbl 1170.68389 · doi:10.1214/074921708000000381
[8] Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations , 3rd edn. Johns Hopkins University Press, Baltimore, MD. · Zbl 0865.65009
[9] Hanschke, T. (1999). A matrix continued fraction algorithm for the multiserver repeated order queue. Math. Comput. Modelling 30, 159-170. · Zbl 1042.60539 · doi:10.1016/S0895-7177(99)00139-9
[10] Knuth, D. E. (1998). The Art of Computer Programming , Vol. 2, 3rd edn. Addison-Wesley. · Zbl 0895.68054
[11] Kumar, S. and Kumar, P. R. (1994). Performance bounds for queueing networks and scheduling policies. IEEE Trans. Automatic Control 39, 1600-1611. · Zbl 0812.90049 · doi:10.1109/9.310033
[12] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . SIAM, Philadelphia, PA. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[13] Morrison, J. R. and Kumar, P. R. (2008). Computational performance bounds for Markov chains with applications. IEEE Trans. Automatic Control 53, 1306-1311. · Zbl 1367.90043 · doi:10.1109/TAC.2008.921013
[14] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[15] Serfozo, R. (2009). Basics of Applied Stochastic Processes . Springer, Berlin. · Zbl 1159.60001 · doi:10.1007/978-3-540-89332-5
[16] Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains . Princeton University Press. · Zbl 0821.65099
[17] 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.
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.