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

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:366

Article

Dudin, Sergei^1,2  Dudin, Alexander^1,2  Kostyukova, Olga³  Dudina, Olga^1,2 

[1] Belarusian State Univ, 4 Nezavisimosti Ave, Minsk 220030, BELARUS

[2] RUDN Univ, Peoples Friendship Univ Russia, 6 Miklukho Maklaya St, Moscow 117198, Russia

[3] Natl Acad Sci Belarus, Inst Math, Minsk, BELARUS

关键词: Level-dependent multi-dimensional;    Markov chains;    Effective algorithm;    Batch Markovian arrival process;    Unreliable service;    Retrial queue;   

DOI  :  10.1016/j.cam.2019.112425

来源: Elsevier

【 摘 要 】

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. (C) 2019 Elsevier B.V. All rights reserved.

【 授权许可】

Free