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

摘要

This paper discusses the error estimation of the last-column-block-augmentednorthwest-corner truncation (LC-block-augmented truncation, for short) ofblock-structured Markov chains (BSMCs) in continuous time. We first deriveupper bounds for the absolute difference between the time-averaged functionalsof a BSMC and its LC-block-augmented truncation, under the assumption that theBSMC satisfies the general $f$-modulated drift condition. We then establishcomputable bounds for a special case where the BSMC is exponentially ergodic.To derive such computable bounds for the general case, we propose a method thatreduces BSMCs to be exponentially ergodic. We also apply the obtained bounds tolevel-dependent quasi-birth-and-death processes (LD-QBDs), and discuss theproperties of the bounds through the numerical results on an M/M/$s$ retrialqueue, which is a representative example of LD-QBDs. Finally, we presentcomputable perturbation bounds for the stationary distribution vectors ofBSMCs.