Spectral analysis of M/G/1 and G/M/1 type Markov chains
Authors:
- 1 March 1996
- journal article
- general applied-probability
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 28 (01) , 114-165
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
This publication has 11 references indexed in Scilit:
- Solutions of the basic matrix equation for M/G/l AND G/M/1 type markov chainsCommunications in Statistics. Stochastic Models, 1994
- A logarithmic reduction algorithm for quasi-birth-death processesJournal of Applied Probability, 1993
- On a Preemptive Markovian Queue with Multiple Servers and Two Priority ClassesMathematics of Operations Research, 1992
- Equilibrium analysis of skip free markov chains: nonlinear matrix equationsCommunications in Statistics. Stochastic Models, 1991
- Robustness of Rootfinding in Single-Server Queueing ModelsINFORMS Journal on Computing, 1990
- Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible SystemsSIAM Review, 1989
- Queues with semi-Markovian arrivalsJournal of Applied Probability, 1967
- Time dependence of queues with semi-Markovian servicesJournal of Applied Probability, 1967
- The single server queue with Poisson input and semi-Markov service timesJournal of Applied Probability, 1966
- Boundaries induced by non-negative matricesTransactions of the American Mathematical Society, 1956