Loading…

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:
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c2988-6dc1af23ae66394a1ff3d42f5bcdbdd3d7e333e2b702c98f446c54d9739961f13
cites
container_end_page 1026
container_issue 6
container_start_page 1018
container_title Operations research
container_volume 39
creator van Dijk, Nico M
description 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.
doi_str_mv 10.1287/opre.39.6.1018
format article
fullrecord <record><control><sourceid>jstor_pasca</sourceid><recordid>TN_cdi_pascalfrancis_primary_5138518</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>171248</jstor_id><sourcerecordid>171248</sourcerecordid><originalsourceid>FETCH-LOGICAL-c2988-6dc1af23ae66394a1ff3d42f5bcdbdd3d7e333e2b702c98f446c54d9739961f13</originalsourceid><addsrcrecordid>eNqFkDtPwzAUhS0EEqWwsrBEgMSU4EfsxGNV8ZKKEFKR2CzXsVuXNg52QsW_JyHlsSCmO5zvnHvvAeAYwQThPLt0ldcJ4QlLEET5DhggillMU0Z2wQBCAmPC0ud9cBDCEkLIKaMDwKe-KZWsrSsjZ6J76V_cWzReSFuGaGPrRTSqqpXtiRDVLnpsdKNtOT8Ee0augj7aziF4ur6ajm_jycPN3Xg0iRXmeR6zQiFpMJGaMcJTiYwhRYoNnaliVhSkyDQhRONZBrHiuUlTpmha8IxwzpBBZAhO-9zKu9dGh1osXePLdqXAiCPcGvIWOvsLQqR9PaOIpy2V9JTyLgSvjai8XUv_LhAUXYei61AQLpjoOmwN59tYGZRcGS9LZcO3iyKS00_spMeWoXb-JzRrr-vUuFdtaZxfh_-XXvT8ws4XG9tqX8YODL_ID-K7lko</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>219124468</pqid></control><display><type>article</type><title>Truncation of Markov Chains with Applications to Queueing</title><source>EBSCOhost Business Source Ultimate</source><source>ABI/INFORM Global (ProQuest)</source><source>Informs</source><source>JSTOR</source><creator>van Dijk, Nico M</creator><creatorcontrib>van Dijk, Nico M</creatorcontrib><description>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.</description><identifier>ISSN: 0030-364X</identifier><identifier>EISSN: 1526-5463</identifier><identifier>DOI: 10.1287/opre.39.6.1018</identifier><identifier>CODEN: OPREAI</identifier><language>eng</language><publisher>Linthicum, MD: INFORMS</publisher><subject>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</subject><ispartof>Operations research, 1991-11, Vol.39 (6), p.1018-1026</ispartof><rights>Copyright 1991 The Operations Research Society of America</rights><rights>1992 INIST-CNRS</rights><rights>Copyright Institute for Operations Research and the Management Sciences Nov/Dec 1991</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c2988-6dc1af23ae66394a1ff3d42f5bcdbdd3d7e333e2b702c98f446c54d9739961f13</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/219124468/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/219124468?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,3678,11668,27903,27904,36039,44342,58217,58450,62593,74642</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=5138518$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>van Dijk, Nico M</creatorcontrib><title>Truncation of Markov Chains with Applications to Queueing</title><title>Operations research</title><description>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.</description><subject>Applications</subject><subject>Applied sciences</subject><subject>Approximation</subject><subject>Error bounds</subject><subject>Exact sciences and technology</subject><subject>finite approximations</subject><subject>Induction assumption</subject><subject>Markov analysis</subject><subject>Markov chains</subject><subject>Markovian</subject><subject>Mathematical models</subject><subject>Modeling</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Operations research</subject><subject>Performance metrics</subject><subject>Probability</subject><subject>Queueing networks</subject><subject>queues</subject><subject>Queuing theory</subject><subject>Queuing theory. Traffic theory</subject><subject>Statistical analysis</subject><subject>Steady states</subject><subject>Studies</subject><subject>tandem</subject><subject>Transition probabilities</subject><subject>Truncation</subject><subject>truncations</subject><issn>0030-364X</issn><issn>1526-5463</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1991</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNqFkDtPwzAUhS0EEqWwsrBEgMSU4EfsxGNV8ZKKEFKR2CzXsVuXNg52QsW_JyHlsSCmO5zvnHvvAeAYwQThPLt0ldcJ4QlLEET5DhggillMU0Z2wQBCAmPC0ud9cBDCEkLIKaMDwKe-KZWsrSsjZ6J76V_cWzReSFuGaGPrRTSqqpXtiRDVLnpsdKNtOT8Ee0augj7aziF4ur6ajm_jycPN3Xg0iRXmeR6zQiFpMJGaMcJTiYwhRYoNnaliVhSkyDQhRONZBrHiuUlTpmha8IxwzpBBZAhO-9zKu9dGh1osXePLdqXAiCPcGvIWOvsLQqR9PaOIpy2V9JTyLgSvjai8XUv_LhAUXYei61AQLpjoOmwN59tYGZRcGS9LZcO3iyKS00_spMeWoXb-JzRrr-vUuFdtaZxfh_-XXvT8ws4XG9tqX8YODL_ID-K7lko</recordid><startdate>19911101</startdate><enddate>19911101</enddate><creator>van Dijk, Nico M</creator><general>INFORMS</general><general>Operations Research Society of America</general><general>Institute for Operations Research and the Management Sciences</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>HJHVS</scope><scope>IBDFT</scope><scope>K30</scope><scope>PAAUG</scope><scope>PAWHS</scope><scope>PAWZZ</scope><scope>PAXOH</scope><scope>PBHAV</scope><scope>PBQSW</scope><scope>PBYQZ</scope><scope>PCIWU</scope><scope>PCMID</scope><scope>PCZJX</scope><scope>PDGRG</scope><scope>PDWWI</scope><scope>PETMR</scope><scope>PFVGT</scope><scope>PGXDX</scope><scope>PIHIL</scope><scope>PISVA</scope><scope>PJCTQ</scope><scope>PJTMS</scope><scope>PLCHJ</scope><scope>PMHAD</scope><scope>PNQDJ</scope><scope>POUND</scope><scope>PPLAD</scope><scope>PQAPC</scope><scope>PQCAN</scope><scope>PQCMW</scope><scope>PQEME</scope><scope>PQHKH</scope><scope>PQMID</scope><scope>PQNCT</scope><scope>PQNET</scope><scope>PQSCT</scope><scope>PQSET</scope><scope>PSVJG</scope><scope>PVMQY</scope><scope>PZGFC</scope><scope>3V.</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X7</scope><scope>7XB</scope><scope>87Z</scope><scope>88E</scope><scope>88F</scope><scope>8AL</scope><scope>8AO</scope><scope>8FE</scope><scope>8FG</scope><scope>8FI</scope><scope>8FJ</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>FYUFA</scope><scope>F~G</scope><scope>GHDGH</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>K9.</scope><scope>L.-</scope><scope>L6V</scope><scope>M0C</scope><scope>M0N</scope><scope>M0S</scope><scope>M1P</scope><scope>M1Q</scope><scope>M2O</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope></search><sort><creationdate>19911101</creationdate><title>Truncation of Markov Chains with Applications to Queueing</title><author>van Dijk, Nico M</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c2988-6dc1af23ae66394a1ff3d42f5bcdbdd3d7e333e2b702c98f446c54d9739961f13</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1991</creationdate><topic>Applications</topic><topic>Applied sciences</topic><topic>Approximation</topic><topic>Error bounds</topic><topic>Exact sciences and technology</topic><topic>finite approximations</topic><topic>Induction assumption</topic><topic>Markov analysis</topic><topic>Markov chains</topic><topic>Markovian</topic><topic>Mathematical models</topic><topic>Modeling</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Operations research</topic><topic>Performance metrics</topic><topic>Probability</topic><topic>Queueing networks</topic><topic>queues</topic><topic>Queuing theory</topic><topic>Queuing theory. Traffic theory</topic><topic>Statistical analysis</topic><topic>Steady states</topic><topic>Studies</topic><topic>tandem</topic><topic>Transition probabilities</topic><topic>Truncation</topic><topic>truncations</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>van Dijk, Nico M</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Periodicals Index Online Segment 19</collection><collection>Periodicals Index Online Segment 27</collection><collection>Periodicals Index Online</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - West</collection><collection>Primary Sources Access (Plan D) - International</collection><collection>Primary Sources Access &amp; Build (Plan A) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Midwest</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Northeast</collection><collection>Primary Sources Access (Plan D) - Southeast</collection><collection>Primary Sources Access (Plan D) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Southeast</collection><collection>Primary Sources Access (Plan D) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - UK / I</collection><collection>Primary Sources Access (Plan D) - Canada</collection><collection>Primary Sources Access (Plan D) - EMEALA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - International</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - International</collection><collection>Primary Sources Access (Plan D) - West</collection><collection>Periodicals Index Online Segments 1-50</collection><collection>Primary Sources Access (Plan D) - APAC</collection><collection>Primary Sources Access (Plan D) - Midwest</collection><collection>Primary Sources Access (Plan D) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Canada</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - EMEALA</collection><collection>Primary Sources Access &amp; Build (Plan A) - APAC</collection><collection>Primary Sources Access &amp; Build (Plan A) - Canada</collection><collection>Primary Sources Access &amp; Build (Plan A) - West</collection><collection>Primary Sources Access &amp; Build (Plan A) - EMEALA</collection><collection>Primary Sources Access (Plan D) - Northeast</collection><collection>Primary Sources Access &amp; Build (Plan A) - Midwest</collection><collection>Primary Sources Access &amp; Build (Plan A) - North Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - Northeast</collection><collection>Primary Sources Access &amp; Build (Plan A) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - Southeast</collection><collection>Primary Sources Access (Plan D) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - APAC</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - MEA</collection><collection>ProQuest Central (Corporate)</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>Health &amp; Medical Collection (Proquest)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Medical Database (Alumni Edition)</collection><collection>Military Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Hospital Premium Collection</collection><collection>Hospital Premium Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>Health Research Premium Collection</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>Health Research Premium Collection (Alumni)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>ProQuest Health &amp; Medical Complete (Alumni)</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ABI/INFORM Global (ProQuest)</collection><collection>Computing Database</collection><collection>Health &amp; Medical Collection (Alumni Edition)</collection><collection>PML(ProQuest Medical Library)</collection><collection>ProQuest Military Database</collection><collection>ProQuest research library</collection><collection>ProQuest Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>van Dijk, Nico M</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Truncation of Markov Chains with Applications to Queueing</atitle><jtitle>Operations research</jtitle><date>1991-11-01</date><risdate>1991</risdate><volume>39</volume><issue>6</issue><spage>1018</spage><epage>1026</epage><pages>1018-1026</pages><issn>0030-364X</issn><eissn>1526-5463</eissn><coden>OPREAI</coden><abstract>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.</abstract><cop>Linthicum, MD</cop><pub>INFORMS</pub><doi>10.1287/opre.39.6.1018</doi><tpages>9</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0030-364X
ispartof Operations research, 1991-11, Vol.39 (6), p.1018-1026
issn 0030-364X
1526-5463
language eng
recordid cdi_pascalfrancis_primary_5138518
source EBSCOhost Business Source Ultimate; ABI/INFORM Global (ProQuest); Informs; JSTOR
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
title Truncation of Markov Chains with Applications to Queueing
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-22T20%3A27%3A49IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_pasca&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Truncation%20of%20Markov%20Chains%20with%20Applications%20to%20Queueing&rft.jtitle=Operations%20research&rft.au=van%20Dijk,%20Nico%20M&rft.date=1991-11-01&rft.volume=39&rft.issue=6&rft.spage=1018&rft.epage=1026&rft.pages=1018-1026&rft.issn=0030-364X&rft.eissn=1526-5463&rft.coden=OPREAI&rft_id=info:doi/10.1287/opre.39.6.1018&rft_dat=%3Cjstor_pasca%3E171248%3C/jstor_pasca%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c2988-6dc1af23ae66394a1ff3d42f5bcdbdd3d7e333e2b702c98f446c54d9739961f13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=219124468&rft_id=info:pmid/&rft_jstor_id=171248&rfr_iscdi=true