×

Linear independence of root equations for \(M/G/1\) type Markov chains. (English) Zbl 0847.60076

Summary: There is a classical technique for determining the equilibrium probabilities of \(M/G/1\) type Markov chains. After transforming the equilibrium balance equations of the chain, one obtains an equivalent system of equations in analytic functions to be solved. This method requires finding all singularities of a given matrix function in the unit disk and then using them to obtain a set of linear equations in the finite number of unknown boundary probabilities. The remaining probabilities and other measures of interest are then computed from the boundary probabilities. Under certain technical assumptions, the linear independence of the resulting equations is established by a direct argument involving only elementary results from matrix theory and complex analysis. Simple conditions for the ergodicity and nonergodicity of the chain are also given.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N.T.J. Bailey, On queueing processes with bulk services, J. Roy. Stat. Soc. XVI (1954) 80-87. · Zbl 0055.36906
[2] E. Çinlar, Time dependence of queues with semi-Markovian services, J. Appl. Prob. 4 (1967) 356-364. · Zbl 0153.19904 · doi:10.2307/3212029
[3] J.F. Hayes,Modeling and Analysis of Computer Communications Networks (Plenum Press, 1984).
[4] R.A. Horn and C.A. Johnson,Matrix Analysis (Cambridge University Press, 1985). · Zbl 0576.15001
[5] J.G. Kemeny, J.L. Snell and A.W. Knapp,Denumerable Markov Chains (Van Nostrand, 1966). · Zbl 0149.13301
[6] A.G. Konheim and M. Reiser, The moveable-boundary multiplexor: Stability and decomposability, in:Teletraffic Analysis and Computer Performance Evaluation, eds. O.J. Boxma, J.W. Cohen and H.C. Tijms (1986) 375-394.
[7] M.F. Neuts, The single server queue with Poisson input and semi-Markov service times, J. Appl. Prob. 3 (1966) 202-230. · Zbl 0204.20003 · doi:10.2307/3212047
[8] M.F. Neuts,Structured Stochastic Matrices of M/G/1 Type and Their Applications (Marcel Dekker, 1989).
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.