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...
Saved in:
Published in: | Operations research 1991-11, Vol.39 (6), p.1018-1026 |
---|---|
Main Author: | |
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&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 & 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 & 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 & 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 & Build (Plan A) - APAC</collection><collection>Primary Sources Access & Build (Plan A) - Canada</collection><collection>Primary Sources Access & Build (Plan A) - West</collection><collection>Primary Sources Access & Build (Plan A) - EMEALA</collection><collection>Primary Sources Access (Plan D) - Northeast</collection><collection>Primary Sources Access & Build (Plan A) - Midwest</collection><collection>Primary Sources Access & Build (Plan A) - North Central</collection><collection>Primary Sources Access & Build (Plan A) - Northeast</collection><collection>Primary Sources Access & Build (Plan A) - South Central</collection><collection>Primary Sources Access & 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 & 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 & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & 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 & 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 & 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 & aerospace journals</collection><collection>ProQuest Advanced Technologies & 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 |