Error bounds for last-column-block-augmented truncations of block-structured Markov chains

DOI10.15807/JORSJ.60.271MaRDI QIDQ4597000zbMATH OpenOpenAlexFDO

Authors Hiroyuki Masuyama

Publication date 11 December 2017

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.03489

zbMATH Keywords

block-structured Markov chainerror boundlast-column block augmented northwest-corner truncationlevel-depedent quasi-birth-and-death processperturbation boundqueue

Mathematics Subject Classification ID

Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Queues and service in operations research (90B22)

Abstract: This paper discusses the error estimation of the last-column-block-augmented northwest-corner truncation (LC-block-augmented truncation, for short) of block-structured Markov chains (BSMCs) in continuous time. We first derive upper bounds for the absolute difference between the time-averaged functionals of a BSMC and its LC-block-augmented truncation, under the assumption that the BSMC satisfies the general $f$-modulated drift condition. We then establish computable bounds for a special case where the BSMC is exponentially ergodic. To derive such computable bounds for the general case, we propose a method that reduces BSMCs to be exponentially ergodic. We also apply the obtained bounds to level-dependent quasi-birth-and-death processes (LD-QBDs), and discuss the properties of the bounds through the numerical results on an M/M/$s$ retrial queue, which is a representative example of LD-QBDs. Finally, we present computable perturbation bounds for the stationary distribution vectors of BSMCs.

Recommendations

• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions
• Error bounds for augmented truncation approximations of Markov chains via the perturbation method
• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under geometric drift conditions
• Continuous-time block-monotone Markov chains and their block-augmented truncations
• Truncation of Markov Chains with Applications to Queueing

Cited in

(12)

• Hoeffding's inequality for Markov processes via solution of Poisson's equation
• Finite-state-space truncations for infinite quasi-birth-death processes
• A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains
• Error bounds for augmented truncation approximations of continuous-time Markov chains
• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions
• Continuous-time block-monotone Markov chains and their block-augmented truncations
• Stationary distributions of continuous-time Markov chains: a review of theory and truncation-based approximations
• Error bounds for augmented truncation approximations of Markov chains via the perturbation method
• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under geometric drift conditions
• A geometric convergence formula for the level-increment-truncation approximation of M/G/1-type Markov chains
• Matrix-Analytic Methods for Solving Poisson’s Equation with Applications to Markov Chains of GI/G/1-Type
• Computable perturbation bounds for augmented truncations of ergodic continuous-time Markov chains

This page was built for publication: Error bounds for last-column-block-augmented truncations of block-structured Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4597000)