2019年6月
A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains
Queueing Systems
- 巻
- 92
- 号
- 1-2
- 開始ページ
- 173
- 終了ページ
- 200
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s11134-019-09599-x
- 出版者・発行元
- Springer Science and Business Media LLC
This paper proposes a new algorithm for computing the stationary distribution vector in continuous-time upper block-Hessenberg Markov chains. To this end, we consider the last-block-column-linearly-augmented (LBCL-augmented) truncation of the (infinitesimal) generator of the upper block-Hessenberg Markov chain. The LBCL-augmented truncation is a linearly augmented truncation such that the augmentation distribution has its probability mass only on the last block column. We first derive an upper bound for the total variation distance between the respective stationary distribution vectors of the original generator and its LBCL-augmented truncation. Based on the upper bound, we then establish a series of linear fractional programming (LFP) problems to obtain augmentation distribution vectors such that the bound converges to zero. Using the optimal solutions of the LFP problems, we construct a matrix-infinite-product (MIP) form of the original (i.e., not approximate) stationary distribution vector and develop a sequential update algorithm for computing the MIP form. Finally, we demonstrate the applicability of our algorithm to BMAP/M/ queues and M/M/s retrial queues.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s11134-019-09599-x
- DBLP
- https://dblp.uni-trier.de/rec/journals/questa/Masuyama19
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000466925200007&DestApp=WOS_CPL
- URL
- http://link.springer.com/article/10.1007/s11134-019-09599-x/fulltext.html
- URL
- http://link.springer.com/content/pdf/10.1007/s11134-019-09599-x.pdf
- ID情報
-
- DOI : 10.1007/s11134-019-09599-x
- ISSN : 0257-0130
- eISSN : 1572-9443
- DBLP ID : journals/questa/Masuyama19
- Web of Science ID : WOS:000466925200007