The time-dependent expected reward and deviation matrix of a finite QBD process. (English) Zbl 1414.60066
Summary: Deriving the time-dependent expected reward function associated with a continuous-time Markov chain involves the computation of its transient deviation matrix. In this paper we focus on the special case of a finite quasi-birth-and-death (QBD) process, motivated by the desire to compute the expected revenue lost in a \(\mathrm{MAP}/\mathrm{PH}/1/C\) queue. We use two different approaches in this context. The first is based on the solution of a finite system of matrix difference equations; it provides an expression for the blocks of the expected reward vector, the deviation matrix, and the mean first passage time matrix. The second approach, based on some results in the perturbation theory of Markov chains, leads to a recursive method to compute the full deviation matrix of a finite QBD process. We compare the two approaches using some numerical examples.
MSC:
| 60J27 | Continuous-time Markov processes on discrete state spaces |
| 15A24 | Matrix equations and identities |
| 47A55 | Perturbation theory of linear operators |
| 15A09 | Theory of matrix inversion and generalized inverses |
| 90B22 | Queues and service in operations research |
Keywords:
finite quasi-birth-and-death process; expected reward; deviation matrix; matrix difference equations; perturbation theoryReferences:
| [1] | Abate, J.; Whitt, W., Numerical inversion of Laplace transforms of probability distributions, ORSA J. Comput., 7, 1, 36-43 (1995) · Zbl 0821.65085 |
| [2] | Altman, E.; Avrachenkov, K. E.; Núnez-Queija, R., Perturbation analysis for denumerable Markov chains with application to queueing models, Adv. in Appl. Probab., 36, 3, 839-853 (2004) · Zbl 1062.60066 |
| [3] | Bini, D.; Dendievel, S.; Latouche, G.; Meini, B., General solution of the Poisson equation for Quasi-Birth-and-Death processes, SIAM J. Appl. Math., 76, 6, 2397-2417 (2016) · Zbl 1352.65124 |
| [4] | Braunsteins, P. T.; Hautphenne, S.; Taylor, P. G., The roles of the deviation matrix and coupling in determining the value of capacity in \(M / M / 1 / C\) queues, Queueing Syst., 83, 1, 157-179 (2016) · Zbl 1341.60109 |
| [5] | Campbell, S. L.; Meyer, C. D., Generalized Inverses of Linear Transformations, Classics Appl. Math., vol. 56 (2009), SIAM · Zbl 1158.15301 |
| [6] | Chiera, B. A.; Taylor, P. G., What is a unit of capacity worth?, Probab. Engrg. Inform. Sci., 16, 4, 513-522 (2002) · Zbl 1038.90017 |
| [7] | Coolen-Schrijner, P.; van Doorn, E. A., The deviation matrix of a continuous-time Markov chain, Probab. Engrg. Inform. Sci., 16, 3, 351-366 (2002) · Zbl 1011.60057 |
| [8] | Da Silva Soares, A.; Latouche, G., The group inverse of finite homogeneous QBD processes, Stoch. Models, 18, 1, 159-171 (2002) · Zbl 1005.60093 |
| [9] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2012), The Johns Hopkins University Press |
| [10] | Hajek, B., Birth-and-death processes on the integers with phases and general boundaries, J. Appl. Probab., 19, 488-499 (1982) · Zbl 0502.60053 |
| [11] | Hunter, J. J., The computation of key properties of Markov chains via perturbations, Linear Algebra Appl., 511, 176-202 (2016) · Zbl 1352.15037 |
| [12] | Jiang, S.; Liu, Y.; Tang, Y., A unified perturbation analysis framework for countable Markov chains, Linear Algebra Appl., 529, 413-440 (2017) · Zbl 1370.60118 |
| [13] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains, vol. 356 (1960), van Nostrand: van Nostrand Princeton, NJ, ISO 690 · Zbl 0089.13704 |
| [14] | Langville, A. N.; Meyer, C. D., Updating Markov chains with an eye on Google’s PageRank, SIAM J. Matrix Anal. Appl., 27, 4, 968-987 (2006) · Zbl 1098.60073 |
| [15] | Latouche, G.; Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling (1999), SIAM · Zbl 0922.60001 |
| [16] | Meyer, C. D., The role of the group generalized inverse in the theory of finite Markov chains, SIAM Rev., 17, 3, 443-464 (1975) · Zbl 0313.60044 |
| [17] | Rising, W., Applications of generalized inverses to Markov chains, Adv. in Appl. Probab., 293, 302 (1991) · Zbl 0724.60080 |
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.
