Truncation of Markov Chains with Applications to Queueing

State-space truncation is frequently demanded for computation of large or infinite Markov chains. Conditions are given that guarantee an error bound or rate of convergence. Roughly, these conditions apply either when probabilities of large states are sufficiently small, or when transition probabilit...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1991-11, Vol.39 (6), p.1018-1026
Main Author: van Dijk, Nico M
Format: Article
Language:English
Subjects:
Applications
Applied sciences
Approximation
Error bounds
Exact sciences and technology
finite approximations
Induction assumption
Markov analysis
Markov chains
Markovian
Mathematical models
Modeling
Operational research and scientific management
Operational research. Management science
Operations research
Performance metrics
Probability
Queueing networks
queues
Queuing theory
Queuing theory. Traffic theory
Statistical analysis
Steady states
Studies
tandem
Transition probabilities
Truncation
truncations
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:State-space truncation is frequently demanded for computation of large or infinite Markov chains. Conditions are given that guarantee an error bound or rate of convergence. Roughly, these conditions apply either when probabilities of large states are sufficiently small, or when transition probabilities (rates) for state increases become small in sufficiently large states. The verification of these conditions is based on establishing bounds for bias terms of reward structures. The conditions and their verification are illustrated by two nonproduct form queueing examples: an overflow model and a tandem queue with blocking. A concrete truncation and explicit error bound are obtained. Some numerical support is provided.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.39.6.1018