A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains
From MaRDI portal
Publication:2281373
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/ queues and M/M/ retrial queues.
Recommendations
- scientific article; zbMATH DE number 1234616
- Effective algorithm for computation of the stationary distribution of multi-dimensional level-dependent Markov chains with upper block-Hessenberg structure of the generator
- Stationary Probabilities Of Markov Chains With Upper Hessenberg Transition Matrices
- A new matrix-infinite-product-form solution for upper block-Hessenberg Markov chains and its quasi-algorithmic constructibility
- Continuous-time block-monotone Markov chains and their block-augmented truncations
Cites work
- AnRG-Factorization Approach for a BMAP/M/1 Generalized Processor-Sharing Queue
- Analysis and computation of the stationary distribution in a special class of Markov chains of level-dependent \(\mathrm{M}/\mathrm{G}/1\)-type and its application to \(\mathrm{BMAP}/\mathrm{M}/\infty\) and \(\mathrm{BMAP}/\mathrm{M}/c+\mathrm{M}\) queues
- Augmented truncations of infinite stochastic matrices
- Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes
- Computing the conditional stationary distribution in Markov chains of level-dependent \(\mathrm{M}/\mathrm{G}/1\)-type
- Continuous-time Markov chains. An applications-oriented approach
- Error bounds for augmented truncation approximations of continuous-time Markov chains
- Error bounds for last-column-block-augmented truncations of block-structured Markov chains
- Fundamental matrix of transient QBD generator with finite states and level dependent transitions
- scientific article; zbMATH DE number 1234616 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- Introduction to Matrix Analytic Methods in Stochastic Modeling
- Markov Chains
- Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory
- New results on the single server queue with a batch markovian arrival process
- On the \(f\)-norm ergodicity of Markov processes in continuous time
- Retrial Queues
- Stochastic block–monotonicity in the approximation of the stationary distribution of infinite markov chains
- Tail asymptotics of the queue size distribution in the M/M/m retrial queue
- The stability condition of BMAP/M/\(\infty\) queues
Cited in
(8)- Subexponential asymptotics of asymptotically block-Toeplitz and upper block-Hessenberg Markov chains
- Effective algorithm for computation of the stationary distribution of multi-dimensional level-dependent Markov chains with upper block-Hessenberg structure of the generator
- scientific article; zbMATH DE number 1234616 (Why is no real title available?)
- Stationary Probabilities Of Markov Chains With Upper Hessenberg Transition Matrices
- APPROXIMATIONS FOR MARKOV CHAINS WITH UPPER HESSENBERG TRANSITION MATRICES
- A Block-GTH Algorithm for Finding the Stationary Vector of a Markov Chain
- On geometric and algebraic transience for block-structured Markov chains
- A new matrix-infinite-product-form solution for upper block-Hessenberg Markov chains and its quasi-algorithmic constructibility
This page was built for publication: A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2281373)
