Spectral analysis ofM/G/1 andG/M/1 type Markov chains
- 1 March 1996
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 28 (1) , 114-165
- https://doi.org/10.2307/1427915
Abstract
When analyzing the equilibrium behavior ofM/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 ofG/M/1 type Markov chains by similar methods is also presented.Keywords
This publication has 12 references indexed in Scilit:
- A logarithmic reduction algorithm for quasi-birth-death processesJournal of Applied Probability, 1993
- 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
- Necessary and sufficient conditions for the ergodicity of Markov chains with transition Δm,n(Δ′m,n)‐matrixInternational Journal of Stochastic Analysis, 1987
- Time dependence of queues with semi-Markovian servicesJournal of Applied Probability, 1967
- Queues with semi-Markovian arrivalsJournal 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
- On Queueing Processes with Bulk ServiceJournal of the Royal Statistical Society Series B: Statistical Methodology, 1954