Skip to main content
SpringerLink
Log in

Linear independence of root equations forM/G/1 type Markov chains

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

There is a classical technique for determining the equilibrium probabilities ofM/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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N.T.J. Bailey, On queueing processes with bulk services, J. Roy. Stat. Soc. XVI (1954) 80–87.

    Google Scholar 

  2. E. Çinlar, Time dependence of queues with semi-Markovian services, J. Appl. Prob. 4 (1967) 356–364.

    Google Scholar 

  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).

  5. J.G. Kemeny, J.L. Snell and A.W. Knapp,Denumerable Markov Chains (Van Nostrand, 1966).

  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.

    Google Scholar 

  8. M.F. Neuts,Structured Stochastic Matrices of M/G/1 Type and Their Applications (Marcel Dekker, 1989).

Download references

Author information

Authors and Affiliations

  1. IBM Thomas J. Watson Research Center, 10598, Yorktown Heights, NY, USA

    H. R. Gail & S. L. Hantler

  2. Technion, IIT, 32000, Haifa, Israel

    M. Sidi

  3. The University of Michigan, 48109, Ann Arbor, MI, USA

    B. A. Taylor

Authors
  1. H. R. Gail
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. L. Hantler
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Sidi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. B. A. Taylor
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gail, H.R., Hantler, S.L., Sidi, M. et al. Linear independence of root equations forM/G/1 type Markov chains. Queueing Syst 20, 321–339 (1995). https://doi.org/10.1007/BF01245323

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01245323

Keywords

Search

Navigation