Hostname: page-component-6bf8c574d5-h6jzd Total loading time: 0.001 Render date: 2025-02-23T12:07:10.580Z Has data issue: false hasContentIssue false
  • English
  • Français

A new matrix-infinite-product-form solution for upper block-Hessenberg Markov chains and its quasi-algorithmic constructibility

Part of: Markov processes

Published online by Cambridge University Press:  29 July 2022

Hiroyuki Masuyama
Hiroyuki Masuyama*
Affiliation:
Tokyo Metropolitan University
*
*Postal address: Graduate School of Management, Tokyo Metropolitan University, Tokyo 192–0397, Japan. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a new matrix-infinite-product-form (MIP-form) solution for the stationary distribution in upper block-Hessenberg Markov chains (UBH-MCs). The existing MIP-form solution (Masuyama, Queueing Systems 92, 2019, pp. 173–200) requires a certain parameter set that satisfies both a Foster–Lyapunov drift condition and a convergence condition. In contrast, the new MIP-form solution requires no such parameter sets and no other conditions. The new MIP-form solution also has ‘quasi-algorithmic constructibility’, which is a newly introduced feature of being constructed by iterating infinitely many times a recursive procedure of finite complexity per iteration. This feature is not found in the other existing solutions for the stationary distribution in general UBH-MCs.

Keywords

Upper block-Hessenberg Markov chain (UBH-MC)level-dependent M/G/1-type Markov chainmatrix-infinite-product-form (MIP-form) solutionquasi-algorithmic constructionstationary distribution vector

MSC classification

Primary: 60J27: Continuous-time Markov processes on discrete state spaces
Secondary: 60J22: Computational methods in Markov chains
Type
Original Article
Information
Advances in Applied Probability , Volume 55 , Issue 1 , March 2023 , pp. 1 - 28
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anderson, W. J. (1991). Continuous-Time Markov Chains: an Applications-Oriented Approach. Springer, New York.CrossRefGoogle Scholar
Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
Baumann, H. and Sandmann, W. (2012). Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1, 1561–1569.CrossRefGoogle Scholar
Brémaud, P. (2020). Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, 2nd edn. Springer, New York.CrossRefGoogle Scholar
Bright, L. and Taylor, P. G. (1995). Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Stoch. Models 11, 497–525.CrossRefGoogle Scholar
Kimura, M. and Takine, T. (2018). Computing the conditional stationary distribution in Markov chains of level-dependent M/G/1-type. Stoch. Models 34, 207–238.CrossRefGoogle Scholar
Kimura, T., Daikoku, K., Masuyama, H. and Takahashi, Y. (2010). Light-tailed asymptotics of stationary tail probability vectors of Markov chains of M/G/1 type. Stoch. Models 26, 505–548.CrossRefGoogle Scholar
Kimura, T., Masuyama, H. and Takahashi, Y. (2013). Subexponential asymptotics of the stationary distributions of GI/G/1-type Markov chains. Stoch. Models 29, 190–239.CrossRefGoogle Scholar
Kimura, T., Masuyama, H. and Takahashi, Y. (2017). Light-tailed asymptotics of GI/G/1-type Markov chains. J. Indust. Manag. Optimization 13, 2093–2146.CrossRefGoogle Scholar
Klimenok, V. and Dudin, A. (2006). Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Systems 54, 245–259.CrossRefGoogle Scholar
Kontoyiannis, I. and Meyn, S. P. (2016). On the f-norm ergodicity of Markov processes in continuous time. Electron. Commun. Prob. 21, paper no. 77, 10 pp.CrossRefGoogle Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, Philadelphia.CrossRefGoogle Scholar
Li, Q.-L., Lian, Z. and Liu, L. (2005). An RG-factorization approach for a BMAP/M/1 generalized processor-sharing queue. Stoch. Models 21, 507–530.CrossRefGoogle Scholar
Masuyama, H. (2016). A sufficient condition for the subexponential asymptotics of GI/G/1-type Markov chains with queueing applications. Ann. Operat. Res. 247, 65–95.CrossRefGoogle Scholar
Masuyama, H. (2017). Continuous-time block-monotone Markov chains and their block-augmented truncations. Linear Algebra Appl. 514, 105–150.CrossRefGoogle Scholar
Masuyama, H. (2019). A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains. Queueing Systems 92, 173–200.CrossRefGoogle Scholar
Phung-Duc, T., Masuyama, H., Kasahara, S. and Takahashi, Y. (2010). 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), Association for Computing Machinery, New York, pp. 46–52.CrossRefGoogle Scholar
Seneta, E. (2006). Non-negative Matrices and Markov Chains. Springer, New York.Google Scholar
Shin, Y. W. and Pearce, C. E. M. (1998). An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form. Korean J. Comput. Appl. Math. 5, 361–384.CrossRefGoogle Scholar
Takine, T. (2016). 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 Systems 84, 49–77.CrossRefGoogle Scholar
Wolf, D. (1980). Approximation of the invariant probability measure of an infinite stochastic matrix. Adv. Appl. Prob. 12, 710–726.CrossRefGoogle Scholar