Continuous-time block-monotone Markov chains and their block-augmented truncations

DOI10.1016/J.LAA.2016.10.014zbMATH Open1349.60127arXiv1511.04669OpenAlexW2268727185MaRDI QIDQ347491FDOQ347491

Hiroyuki Masuyama

Publication date: 30 November 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: This paper considers continuous-time block-monotone Markov chains (BMMCs) and their block-augmented truncations. We first introduce the block monotonicity and block-wise dominance relation for continuous-time Markov chains, and then provide some fundamental results on the two notions. Using these results, we show that the stationary distribution vectors obtained by the block-augmented truncation converge to the stationary distribution vector of the original BMMC. We also show that the last-column-block-augmented truncation (LC-block-augmented truncation) provides the best (in a certain sense) approximation to the stationary distribution vector of a BMMC among all the block-augmented truncations. Furthermore, we present computable upper bounds for the total variation distance between the stationary distribution vectors of a Markov chain and its LC-block-augmented truncation, under the assumption that the original Markov chain itself may not be block-monotone but is block-wise dominated by a BMMC with exponential ergodicity. Finally, we apply the obtained bounds to a queue with a batch Markovian arrival process and state-dependent departure rates.

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

Recommendations

• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions
• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under geometric drift conditions
• Error bounds for last-column-block-augmented truncations of block-structured Markov chains
• Augmented truncation approximations of discrete-time Markov chains
• Stochastic block–monotonicity in the approximation of the stationary distribution of infinite markov chains

zbMATH Keywords

exponential ergodicity\(\mathrm{GI}/\mathrm{G}/1\)-type Markov chainblock-augmented truncationblock-monotone Markov chainlevel-dependent QBD (LD-QBD)total-variation-distance error bound

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• A first course in stochastic models.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Markov chains and stochastic stability
• Comparison methods for stochastic models and risks
• Probability with Martingales
• Numerical Methods for Structured Markov Chains
• New results on the single server queue with a batch markovian arrival process
• On truncations for weakly ergodic inhomogeneous birth and death processes
• Continuous-time Markov chains. An applications-oriented approach
• Markov Chains
• Perturbation bounds and truncations for a class of Markovian queues
• Derivatives of Eigenvalues and Eigenvectors of Matrix Functions
• Title not available (Why is that?)
• Augmented truncation approximations of discrete-time Markov chains
• Approximating Markov chains and \(V\)-geometric ergodicity via weak perturbation theory
• A CONVEXITY PROPERTY OF POSITIVE MATRICES
• Title not available (Why is that?)
• Perturbation Bounds forM_t/M_t/NQueue with Catastrophes
• Computable exponential convergence rates for stochastically ordered Markov processes
• Monotone infinite stochastic matrices and their augmented truncations
• Error Bounds for Augmented Truncations of Discrete-Time Block-Monotone Markov Chains under Subgeometric Drift Conditions
• Truncation approximations of invariant measures for Markov chains
• Title not available (Why is that?)
• Stochastic block–monotonicity in the approximation of the stationary distribution of infinite markov chains
• Error Bounds for Augmented Truncations of Discrete-Time Block-Monotone Markov Chains under Geometric Drift Conditions
• Stochastically monotone Markov Chains

Cited In (10)

• Error bounds for augmented truncation approximations of Markov chains via the perturbation method
• 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
• Numerical Methods for Integral Equations of the Second Kind with NonSmooth Solutions of Bounded Variation
• Stochastic block–monotonicity in the approximation of the stationary distribution of infinite markov chains
• Two-Sided Truncations for a Class of Continuous-Time Markov Chains
• Stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices and their applications to queueing systems
• Perturbation analysis for continuous-time Markov chains in a weak sense
• A new matrix-infinite-product-form solution for upper block-Hessenberg Markov chains and its quasi-algorithmic constructibility
• Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations

Uses Software

• MCQueue

This page was built for publication: Continuous-time block-monotone Markov chains and their block-augmented truncations

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