Stationary probabilities of Markov chains with upper Hessenberg transition matrices

In this paper, based on probabilistic arguments, we obtain an explicit solution of the stationary distribution for a discrete time Markov chain with an upper Hessenberg time stationary transition probability matrix. Our solution then leads to a numerically stable and efficient algorithm for computing stationary probabilities. Two other expressions for the stationary distribution are also derived, which lead to two alternative algorithms. Numerical analysis of the algorithms is given, which shows the reliability and efficiency of the algorithms. Examples of applications are provided, including results of a discrete time state dependent batch arrive queueing model. The idea used in this paper can be generalized to deal with Markov chains with a more general structure.