In this paper we consider systems which are generalizations of the standard quasi-birth-and-death processes (QBDs) in two directions. We allow transition probabilities to be level-dependent and there to be possibly infinitely many phases at each level. Our first results are explicit expressions for the matrices Gk, containing the probabilities that a process first reaches level k − 1 in phase j, given that it starts in phase i of level k, and Rk, containing the expected number of visits to phase j of level k + 1 before first return to level k given that the process starts in phase i of level k. From these expressions, a generalization of the well-known matrix-geometric stationary distribution for finite-phase, level-independent processes can be deduced. Thus we have established a basis for the algorithmic analysis of level-dependent QBDs. We further give necessary and sufficient conditions for a vector x to be a right eigenvector of Gk for all k, and for xT to be a left eigenvector of Rk. The potential uses of these results are manyfold. For level-independent QBDs, they provide a characterization of all the eigenvectors and eigenvalues of G and, in the positive recurrent case, R. They have also been used by the authors in applying matrix-analytic methods to networks of queues. There a relationship is shown to exist between eigenvector–eigenvalue pairs of Rk and solutions of the standard traffic equations for these networks.
