Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains

  • Published:
Queueing Systems Aims and scope Submit manuscript

A Correction to this article was published on 04 April 2019

This article has been updated

Abstract

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/\(\infty \) queues and M/M/s retrial queues.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Change history

  • 04 April 2019

    The original version of this article unfortunately contained the following errors: In Introduction, below Eq. (1.3), the sentence should read “From (1.2) and (1.3), we have” instead of “From (1.2) and (1.6), we have”.

References

  1. Anderson, W.J.: Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer, New York (1991)

    Book  Google Scholar 

  2. Baumann, H., Sandmann, W.: Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1(1), 1561–1569 (2012)

    Article  Google Scholar 

  3. Brémaud, P.: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York (1999)

    Book  Google Scholar 

  4. Bright, L., Taylor, P.G.: Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Stoch. Models 11(3), 497–525 (1995)

    Article  Google Scholar 

  5. Falin, G.I., Templeton, J.G.C.: Retrial Queues. Chapman & Hall, London (1997)

    Book  Google Scholar 

  6. Gibson, D., Seneta, E.: Augmented truncations of infinite stochastic matrices. J. Appl. Probab. 24(3), 600–608 (1987)

    Article  Google Scholar 

  7. Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)

    Google Scholar 

  8. Kim, J., Kim, J., Kim, B.: Tail asymptotics of the queue size distribution in the M/M/\(m\) retrial queue. J. Comput. Appl. Math. 236(14), 3445–3460 (2012)

    Article  Google Scholar 

  9. Kimura, M., Takine, T.: Private communication (2016)

  10. Kimura, M., Takine, T.: Computing the conditional stationary distribution in Markov chains of level-dependent M/G/1-type. Stoch. Models 34(2), 207–238 (2018)

    Article  Google Scholar 

  11. Klimenok, V., Dudin, A.: Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Syst. 54(4), 245–259 (2006)

    Article  Google Scholar 

  12. Kontoyiannis, I., Meyn, S.P.: On the \(f\)-norm ergodicity of Markov processes in continuous time. Electron. Commun. Probab. 21, Paper no. 77, 1–10 (2016)

  13. Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia, PA (1999)

    Book  Google Scholar 

  14. Le Boudec, J.Y.: An efficient solution method for Markov models of ATM links with loss priorities. IEEE J. Sel. Areas Commun. 9(3), 408–417 (1991)

    Article  Google Scholar 

  15. Li, H., Zhao, Y.Q.: Stochastic block-monotonicity in the approximation of the stationary distribution of infinite Markov chains. Stoch. Models 16(2), 313–333 (2000)

    Article  Google Scholar 

  16. Li, Q.L., Lian, Z., Liu, L.: An \(RG\)-factorization approach for a BMAP/M/1 generalized processor-sharing queue. Stoch. Models 21(2–3), 507–530 (2005)

    Article  Google Scholar 

  17. Liu, Y., Li, W., Masuyama, H.: Error bounds for augmented truncation approximations of continuous-time Markov chains. Oper. Res. Lett. 46(4), 409–413 (2018)

    Article  Google Scholar 

  18. Lucantoni, D.M.: New results on the single server queue with a batch Markovian arrival process. Stoch. Models 7(1), 1–46 (1991)

    Article  Google Scholar 

  19. Masuyama, H.: Limit formulas for the normalized fundamental matrix of the northwest-corner truncation of Markov chains: Matrix-infinite-product-form solutions of block-Hessenberg Markov chains (2016). Preprint arXiv:1603.07787

  20. Masuyama, H.: Error bounds for last-column-block-augmented truncations of block-structured Markov chains. J. Oper. Res. Soc. Jpn. 60(3), 271–320 (2017)

    Article  Google Scholar 

  21. Phung-Duc, T., Masuyama, H., Kasahara, S., Takahashi, Y.: A simple algorithm for the rate matrices of level-dependent QBD processes. In: Proceedings of the 5th International Conference on Queueing Theory and Network Applications (QTNA2010), pp. 46–52. ACM, New York (2010)

  22. Shin, Y.W.: Fundamental matrix of transient QBD generator with finite states and level dependent transitions. Asia-Pac. J. Oper. Res. 26(5), 697–714 (2009)

    Article  Google Scholar 

  23. Shin, Y.W., Pearce, C.E.M.: An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form. Korean J. Comput. Appl. Math. 5(2), 361–384 (1998)

    Google Scholar 

  24. Takine, T.: Analysis and computation of the stationary distribution in a special class of Markov chains of level-dependent M/G/1-type and its application to BMAP/M/\(\infty \) and BMAP/M/\(c+M\) queues. Queueing Syst. 84(1–2), 49–77 (2016)

    Article  Google Scholar 

  25. Yajima, M., Phung-Duc, T., Masuyama, H.: The stability condition of BMAP/M/\(\infty \) queues. In: Proceedings of the 11th International Conference on Queueing Theory and Network Applications (QTNA2016), Article no. 5, pp. 1–6. ACM, New York (2016)

Download references

Acknowledgements

The author thanks Mr. Masatoshi Kimura and Dr. Tetsuya Takine for providing the counterexample presented in Sect. 2.3. The author also thanks an anonymous referee for his/her valuable comments that helped to improve the paper.

Author information

Authors and Affiliations

  1. Department of Systems Science, Graduate School of Informatics, Kyoto University, Kyoto, 606-8501, Japan

    Hiroyuki Masuyama

Authors
  1. Hiroyuki Masuyama
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hiroyuki Masuyama.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was supported in part by JSPS KAKENHI Grant Number JP18K11181.

The original version of this article was revised: The errors in the text, equation citations, equation layout and reference have been corrected.

Appendix A: Proof of Proposition 3.1

Appendix A: Proof of Proposition 3.1

Let \(\varvec{T}_n^*\), \(n \in \mathbb {Z}_+\), denote

$$\begin{aligned} \varvec{T}_n^* = \left\{ \begin{array}{ll} \varvec{Q}_{0,0}, &{}\quad n=0,\\ \varvec{Q}_{n,n} + \displaystyle \sum _{\ell =0}^{n-1} \varvec{U}_{n,\ell } \varvec{Q}_{\ell ,n}, &{}\quad n \in \mathbb {N}. \end{array} \right. \end{aligned}$$
(A.1)

It then follows from (2.11), (3.9), and (A.1) that

$$\begin{aligned} \varvec{\pi }_n\varvec{\varDelta }_n \ge \varvec{\pi }_n(-\varvec{Q}_{n,n}) \ge \varvec{\pi }_n(-\varvec{T}_n^*) = \varvec{\pi }_n(\varvec{U}_n^*)^{-1}, \quad n \in \mathbb {Z}_+. \end{aligned}$$
(A.2)

It also follows from (2.14), (A.1), and \(\sum _{\ell =0}^{\infty } \varvec{\pi }_{\ell } \varvec{Q}_{\ell ,n} = \varvec{0}\) (\(n\in \mathbb {Z}_+\)) that

$$\begin{aligned} \varvec{\pi }_n(-\varvec{T}_n^*)= & {} -\varvec{\pi }_n \varvec{Q}_{n,n} -\varvec{\pi }_n \displaystyle \sum _{\ell =0}^{n-1} \varvec{U}_{n,\ell } \varvec{Q}_{\ell ,n} \nonumber \\= & {} - \sum _{\ell =0}^n \varvec{\pi }_{\ell } \varvec{Q}_{\ell ,n} = \sum _{\ell =n+1}^{\infty } \varvec{\pi }_{\ell } \varvec{Q}_{\ell ,n} \ge \varvec{0},\ne \varvec{0},\quad n \in \mathbb {Z}_+. \end{aligned}$$
(A.3)

Combining (A.2) and (A.3) yields (3.11). The proof has been completed.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Masuyama, H. A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains. Queueing Syst 92, 173–200 (2019). https://doi.org/10.1007/s11134-019-09599-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-019-09599-x

Keywords

Mathematics Subject Classification

Search

Navigation