Sufficient Conditions for Positive Recurrence and Recurrence of Specially Structured Markov Chains

This paper considers a specially structured Markov chain that arises naturally in certain queuing problems. Sufficient conditions for positive recurrence and recurrence are obtained using the concept of conditional expected one-step displacement of the chain. The proof makes use of the fundamental dual theorem of linear programming. A numerical example is given showing that the sufficient conditions are not necessary. The results of this paper apply to certain aspects of previous work by Harris on “Queues with State Dependent Stochastic Service Rates,” (1967) in this Journal. Specifically, the results of this paper generalize the sufficient conditions for recurrence given by Theorems 1 and 2 of that paper.