ERROR BOUNDS FOR LAST-COLUMN-BLOCK-AUGMENTED TRUNCATIONS OF BLOCK-STRUCTURED MARKOV CHAINS
From MaRDI portal
Publication:4597000
DOI10.15807/JORSJ.60.271zbMath1387.90069arXiv1601.03489OpenAlexW2234119470MaRDI QIDQ4597000
Publication date: 11 December 2017
Published in: Journal of the Operations Research Society of Japan (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1601.03489
error boundqueueperturbation boundblock-structured Markov chainlast-column block augmented northwest-corner truncationlevel-depedent quasi-birth-and-death process
Queues and service in operations research (90B22) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)
Related Items (9)
Error Bounds for Augmented Truncations of Discrete-Time Block-Monotone Markov Chains under Subgeometric Drift Conditions ⋮ Error bounds for augmented truncation approximations of continuous-time Markov chains ⋮ 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 ⋮ Finite-state-space truncations for infinite quasi-birth-death processes ⋮ Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations ⋮ A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains ⋮ Error bounds for augmented truncation approximations of Markov chains via the perturbation method ⋮ Hoeffding's inequality for Markov processes via solution of Poisson's equation
This page was built for publication: ERROR BOUNDS FOR LAST-COLUMN-BLOCK-AUGMENTED TRUNCATIONS OF BLOCK-STRUCTURED MARKOV CHAINS
