Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-23T23:16:35.668Z Has data issue: false hasContentIssue false
  • English
  • Français

Spectral analysis of M/G/1 and G/M/1 type Markov chains

Part of: Computer system organization Operations research and management science Special processes Markov processes

Published online by Cambridge University Press:  01 July 2016

H. R. Gail ,
S. L. Hantler  and
B. A. Taylor
H. R. Gail*
Affiliation:
IBM Thomas J. Watson Research Center
S. L. Hantler*
Affiliation:
IBM Thomas J. Watson Research Center
B. A. Taylor*
Affiliation:
The University of Michigan
*
* Postal address: IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA.
* Postal address: IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA.
** Postal address: The University of Michigan, Ann Arbor, MI 48109, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

When analyzing the equilibrium behavior of M/G/1 type Markov chains by transform methods, restrictive hypotheses are often made to avoid technical problems that arise in applying results from complex analysis and linear algebra. It is shown that such restrictive assumptions are unnecessary, and an analysis of these chains using generating functions is given under only the natural hypotheses that first moments (or second moments in the null recurrent case) exist. The key to the analysis is the identification of an important subspace of the space of bounded solutions of the system of homogeneous vector-valued Wiener–Hopf equations associated with the chain. In particular, the linear equations in the boundary probabilities obtained from the transform method are shown to correspond to a spectral basis of the shift operator on this subspace. Necessary and sufficient conditions under which the chain is ergodic, null recurrent or transient are derived in terms of properties of the matrix-valued generating functions determined by transitions of the Markov chain. In the transient case, the Martin exit boundary is identified and shown to be associated with certain eigenvalues and vectors of one of these generating functions. An equilibrium analysis of the class of G/M/1 type Markov chains by similar methods is also presented.

Keywords

MARTIN EXIT BOUNDARYTRANSFORM METHODSMATRIX-ANALYTIC METHODSRANDOM WALKSHIFT OPERATORWIENER–HOPF EQUATIONS

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 68M20: Performance evaluation; queueing; scheduling 90B22: Queues and service
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 28 , Issue 1 , March 1996 , pp. 114 - 165
Copyright
Copyright © Applied Probability Trust 1996 

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

References

[1] Abolnikov, L. and Dukhovny, A. (1987) Necessary and sufficient conditions for the ergodicity of Markov chains with transition ?m,n (?'m,n)-matrix. J. Appl. Math. Simul. 1, 13–24.CrossRefGoogle Scholar
[2] Asmussen, S. (1987) Applied Probability and Queues. Wiley, New York.Google Scholar
[3] Bailey, N. T. J. (1954) On queueing processes with bulk service. J. Royal Stat. Soc. B 16, 80–87.Google Scholar
[4] Chaudhry, M. L., Harris, C. M. and Marchal, W. G. (1990) Robustness of rootfinding in single-server queueing models. ORSA J. Comput 2, 273–286.CrossRefGoogle Scholar
[5] ÇInlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.CrossRefGoogle Scholar
[6] ÇInlar, E. (1967) Queues with semi-Markovian arrivals. J. Appl. Prob. 4, 365–379.CrossRefGoogle Scholar
[7] Daigle, J. N. and Lucantoni, D. M. (1991) Queueing systems having phase-dependent arrival and service rates. In Numerical Solution of Markov Chains. pp. 161–202. ed. Stewart, W. J. Marcel Dekker, New York.Google Scholar
[8] Feller, W. (1956) Boundaries induced by non-negative matrices. Trans. Amer. Math. Soc. 83, 19–54.CrossRefGoogle Scholar
[9] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1992) On a preemptive Markovian queue with multiple servers and two priority classes. Math. Operat. Res. 17, 365–391.CrossRefGoogle Scholar
[10] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1992) Spectral analysis of M/G/1 type Markov chains. IBM Research Report RC 17765.Google Scholar
[11] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1994) Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chains. Commun. Statist. Stoch. Models 10, 1–43.CrossRefGoogle Scholar
[12] Gantmacher, F. R. (1959) Applications of the Theory of Matrices. Interscience, New York.Google Scholar
[13] Gohberg, I. C. and Fel'Dman, I. A. (1974) Convolution Equations and Projection Methods for their Solution. American Mathematical Society, Providence, RI.Google Scholar
[14] Gohberg, I., Lancaster, P. and Rodman, L. (1982) Matrix Polynomials. Academic Press, New York.Google Scholar
[15] Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1966) Denumerable Markov Chains. Van Nostrand, New York.Google Scholar
[16] Latouche, G. and Ramaswami, V. (1993) A logarithmic reduction algorithm for quasi-birth-death processes. J. Appl. Prob. 30, 650–674.CrossRefGoogle Scholar
[17] Meyer, C. D. (1989) Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Rev. 31, 240–272.CrossRefGoogle Scholar
[18] Mitrani, I. and Mitra, D. (1992) A spectral expansion method for random walks on semi-infinite strips. In Iterative Methods in Linear Algebra. pp. 141–149. ed. Beauwens, R. and de Groen, P. North-Holland, Amsterdam.Google Scholar
[19] Murthy, G. R., Kim, M. and Coyle, E. J. (1991) Equilibrium analysis of skip free Markov chains: nonlinear matrix equations. Commun. Statist. Stoch. Models 7, 547–571.CrossRefGoogle Scholar
[20] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.CrossRefGoogle Scholar
[21] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. The Johns Hopkins University Press, Baltimore.Google Scholar
[22] Neuts, M. F. (1989) Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York.Google Scholar