In this paper the authors consider systems which are generalizations of the standard quasi-birth-and-death processes (QBDs) in two directions. They allow transition probabilities to be level-dependent and there to be possibly infinitely many phases at each level. The present 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 the authors have established a basis for the algorithmic analysis of level-dependent QBDs. They 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. Their a relationship is shown to exist between eigenvector-eigenvalue pairs of Rk and solutions of the standard traffic equations for these networks.
