Effective algorithm for computation of the stationary distribution of multi-dimensional level-dependent Markov chains with upper block-Hessenberg structure of the generator

Abstract

Multi-dimensional level-dependent Markov chains with the upper block-Hessenberg structure of the generator have found extensive applications in applied probability for solving the problems of queueing, reliability, inventory, etc. However, the problem of computing the stationary distribution of such chains is not completely solved. There is a known algorithm for multi-dimensional Asymptotically Quasi-Toeplitz Markov Chains, but, it is required a large amount of computer resources and time-consuming. In this paper, we propose a new effective algorithm that is much less time- and memory-consuming. The new algorithm can be used for analyzing any multi-dimensional Markov chain with the considered structure of the generator. To numerically demonstrate the advantages of this algorithm over the known one, we use it for analysis of a novel single-server retrial queueing system with the batch Markovian arrival process (BMAP), a finite buffer, non-persistent customers and an unreliable server. We derive a transparent ergodicity condition for this queueing system. Then, assuming that this condition is fulfilled, we apply the new algorithm and demonstrate its advantages over the known one.