Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-11T00:55:18.929Z Has data issue: false hasContentIssue false
  • English
  • Français

Markov chains with applications in queueing theory, which have a matrix-geometric invariant probability vector

Published online by Cambridge University Press:  01 July 2016

Marcel F. Neuts
Marcel F. Neuts*
Affiliation:
University of Delaware
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that a class of infinite, block-partitioned, stochastic matrices has a matrix-geometric invariant probability vector of the form (x0, x1,…), where xk = x0Rk, for k ≧ 0. The rate matrix R is an irreducible, non-negative matrix of spectral radius less than one. The matrix R is the minimal solution, in the set of non-negative matrices of spectral radius at most one, of a non-linear matrix equation.

Applications to queueing theory are discussed. Detailed explicit and computationally tractable solutions for the GI/PH/1 and the SM/M/1 queue are obtained.

Keywords

STOCHASTIC MATRICESMARKOV CHAINSMARKOV RENEWAL PROCESSESCOMPUTATIONAL PROBABILITYPROBABILITY DISTRIBUTIONS OF PHASE TYPEGI/PH/1SM/M/1NON-LINEAR MATRIX EQUATIONS

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 10 , Issue 1 , March 1978 , pp. 185 - 212
Copyright
Copyright © Applied Probability Trust 1978 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

This research was sponsored by the Air Force Office of Scientific Research Air Force Systems Command USAF, under Grants Nos. AFOSR-72-2350 B and AFOSR-77-3256.

References

[1] Bellman, R. (1960) Introduction to Matrix Analysis. McGraw-Hill, New York.Google Scholar
[2] Carson, C. C. (1975) Computational Methods for Single Server Queues with Interarrival and Service Time Distributions of Phase Type. Ph.D. Thesis, Purdue University.Google Scholar
[3] Çinlar, E. (1967) Queues with semi-Markovian arrivals. J. Appl. Prob. 4, 365–379.Google Scholar
[4] Çinlar, E. (1969) Markov renewal theory. Adv. Appl. Prob. 1, 123–187.Google Scholar
[5] Gantmacher, F. R. (1959) The Theory of Matrices, Vol. I. Chelsea, New York.Google Scholar
[6] Hunter, J. J. (1969) On the moments of Markov renewal processes Adv. Appl. Prob. 1, 188–210.Google Scholar
[7] Karlin, S. (1969) A First Course in Stochastic Processes. Academic Press, New York.Google Scholar
[8] Kingman, J. F. C. (1961) A convexity property of positive matrices. Quart. J. Math. 12, 283–284.Google Scholar
[9] Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston.Google Scholar
[10] Neuts, M. F. (1975) Probability distributions of phase type. In Liber Amicorum Professor Emeritus H. Florin, Department of Mathematics, University of Louvain, Belgium, 173–206.Google Scholar
[11] Neuts, M. F. (1975) Computational uses of the method of phases in the theory of queues. Computers Math. Appl. 1, 151–166.Google Scholar
[12] Neuts, M. F. (1975) Computational problems related to the Galton–Watson process. Proceedings of Actuarial Research Conference, Brown University, 1975. To appear.Google Scholar
[13] Neuts, M. F. (1977) Algorithms for the waiting time distributions under various queue disciplines in the M/G/1 queue with service time distributions of phase type. In TIMS–North Holland Studies in Management Science No. 7, Algorithmic Methods in Probability.Google Scholar
[14] Neuts, M. F. (1976) Moment formulas for the Markov renewal branching process. Adv. Appl. Prob. 8, 690–711.Google Scholar
[15] Neuts, M. F. (1977) Some explicit formulas for the steady-state behavior of the queue with semi-Markovian service times. Adv. Appl. Prob. 9, 141–157.Google Scholar
[16] Neuts, M. F. (1976) Renewal processes of phase type. Mimeograph Series No. 8/76, Department of Statistics and Computer Science, University of Delaware.Google Scholar
[17] Wallace, V. (1969) The Solution of Quasi Birth and Death Processes Arising from Multiple Access Computer Systems. Ph.D. Thesis, University of Michigan, Ann Arbor, Tech. Rept. No. 07742-6-T.Google Scholar