Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-30T19:31:46.577Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximations to quasi-birth-and-death processes with infinite blocks

Part of: Markov processes

Published online by Cambridge University Press:  01 July 2016

Nigel Bean  and
Guy Latouche
Nigel Bean*
Affiliation:
University of Adelaide
Guy Latouche*
Affiliation:
Université Libre de Bruxelles
*
∗ Postal address: Department of Applied Mathematics, University of Adelaide, SA 5005, Australia. Email address: [email protected]
∗∗ Postal address: Département d'Informatique, Université Libre de Bruxelles, Campus Plaine, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium.
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.

The numerical analysis of quasi-birth-and-death processes rests on the resolution of a matrix-quadratic equation for which efficient algorithms are known when the matrices have finite order, that is, when the number of phases is finite. In this paper we consider the case of infinitely many phases from the point of view of theoretical convergence of truncation and augmentation schemes, and we develop four different methods. Two methods rely on forced transitions to the boundary. In one of these methods, the transitions occur as a result of the truncation itself, while in the other method, they are artificially introduced so that the augmentation may be chosen to be as natural as possible. Two other methods rely on forced transitions within the same level. We conclude with a brief numerical illustration.

Keywords

Quasi-birth-and-death processinfinite-dimensional matrixtruncation and augmentationapproximationsmatrix-analytic method

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 60J22: Computational methods in Markov chains
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 42 , Issue 4 , December 2010 , pp. 1102 - 1125
Copyright
Copyright © Applied Probability Trust 2010 

References

Bini, D. A., Latouche, G. and Meini, B. (2005). Numerical Methods for Structured Markov Chains. Oxford University Press.CrossRefGoogle Scholar
Çinlar, E. (1975). Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Gibson, D. and Seneta, E. (1987). Augmented truncation of infinite stochastic matrices. J. Appl. Prob. 24, 600–608.Google Scholar
Heyman, D. P. and Whitt, W. (1989). Limits for queues as the waiting room grows. Queueing Systems 5, 381–392.CrossRefGoogle Scholar
Kroese, D. P., Scheinhardt, W. R. W. and Taylor, P. G. (2004). Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. Ann. Appl. Prob. 14, 2057–2089.CrossRefGoogle Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia PA.CrossRefGoogle Scholar
Latouche, G. and Taylor, P. G. (2002). Truncation and augmentation of level-independent QBD processes. Stoch. Proces. Appl. 99, 53–80.Google Scholar
Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD.Google Scholar
Ramaswami, V. and Taylor, P. G. (1996). An operator-analytic approach to product-form networks. Commun. Statist. Stoch. Models 12, 121–142.Google Scholar
Seneta, E. (1980). Computing the stationary distribution for infinite Markov chains. Linear Algebra Appl. 34, 259–267.CrossRefGoogle Scholar
Wolf, D. (1980). Approximation of the invariant probability measure of an infinite stochastic matrix. Adv. Appl. Prob. 12, 710–726.CrossRefGoogle Scholar
Zhao, Y. Q. and Liu, D. (1996). The censored Markov chain and the best augmentation. J. Appl. Prob. 33, 623–629.Google Scholar