Computing Cumulative Measures of Stiff Markov Chains Using Aggregation

Andrea Bobbio; Kishor Trivedi

doi:10.1109/12.59859

Computing Cumulative Measures of Stiff Markov Chains Using Aggregation

Andrea Bobbio
, Kishor Trivedi

Research output: Contribution to journal › Article › peer-review

Abstract

We present an aggregation method for the computation of transient cumulative measures of large, stiff Markov models. The method is based on the classification of the states of the original problem into slow, fast transient, and fast recurrent states. We aggregate fast transient states and fast recurrent states so that an approximate value to the desired cumulative measure can be obtained by solving a nonstiff set of linear differential equations defined over a reduced subset of slow states only. Several examples are included to illustrate how stiffness arises naturally in actual queueing and reliability models, and to show that cumulative measures provide a better characterization of the time dependent system behavior.

Original language	English
Pages (from-to)	1291-1298
Number of pages	8
Journal	IEEE Transactions on Computers
Volume	39
Issue number	10
DOIs	https://doi.org/10.1109/12.59859
Publication status	Published - Oct 1990
Externally published	Yes

Keywords

Aggregation
Markov chains
decomposition
queueing networks
reliability models
stiffness
transient analysis

Access to Document

10.1109/12.59859

Cite this

@article{aa434a666cc94a84bd78ab34aa8c499a,

title = "Computing Cumulative Measures of Stiff Markov Chains Using Aggregation",

abstract = "We present an aggregation method for the computation of transient cumulative measures of large, stiff Markov models. The method is based on the classification of the states of the original problem into slow, fast transient, and fast recurrent states. We aggregate fast transient states and fast recurrent states so that an approximate value to the desired cumulative measure can be obtained by solving a nonstiff set of linear differential equations defined over a reduced subset of slow states only. Several examples are included to illustrate how stiffness arises naturally in actual queueing and reliability models, and to show that cumulative measures provide a better characterization of the time dependent system behavior.",

keywords = "Aggregation, Markov chains, decomposition, queueing networks, reliability models, stiffness, transient analysis",

author = "Andrea Bobbio and Kishor Trivedi",

note = "Funding Information: Manuscript received October 10, 1987; revised March 3, 1988. This work was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-84-0132, by the U.S. Army Research Office under Grant DAA629-84-0045, and by the Italian National Research Council CNR under the Project: “Materials and Devices for Solid-state Electronics,” Grant 86.02177.61.",

year = "1990",

month = oct,

doi = "10.1109/12.59859",

language = "English",

volume = "39",

pages = "1291--1298",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "10",

}

TY - JOUR

T1 - Computing Cumulative Measures of Stiff Markov Chains Using Aggregation

AU - Bobbio, Andrea

AU - Trivedi, Kishor

N1 - Funding Information: Manuscript received October 10, 1987; revised March 3, 1988. This work was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-84-0132, by the U.S. Army Research Office under Grant DAA629-84-0045, and by the Italian National Research Council CNR under the Project: “Materials and Devices for Solid-state Electronics,” Grant 86.02177.61.

PY - 1990/10

Y1 - 1990/10

N2 - We present an aggregation method for the computation of transient cumulative measures of large, stiff Markov models. The method is based on the classification of the states of the original problem into slow, fast transient, and fast recurrent states. We aggregate fast transient states and fast recurrent states so that an approximate value to the desired cumulative measure can be obtained by solving a nonstiff set of linear differential equations defined over a reduced subset of slow states only. Several examples are included to illustrate how stiffness arises naturally in actual queueing and reliability models, and to show that cumulative measures provide a better characterization of the time dependent system behavior.

AB - We present an aggregation method for the computation of transient cumulative measures of large, stiff Markov models. The method is based on the classification of the states of the original problem into slow, fast transient, and fast recurrent states. We aggregate fast transient states and fast recurrent states so that an approximate value to the desired cumulative measure can be obtained by solving a nonstiff set of linear differential equations defined over a reduced subset of slow states only. Several examples are included to illustrate how stiffness arises naturally in actual queueing and reliability models, and to show that cumulative measures provide a better characterization of the time dependent system behavior.

KW - Aggregation

KW - Markov chains

KW - decomposition

KW - queueing networks

KW - reliability models

KW - stiffness

KW - transient analysis

UR - https://www.scopus.com/pages/publications/0025508090

U2 - 10.1109/12.59859

DO - 10.1109/12.59859

M3 - Article

SN - 0018-9340

VL - 39

SP - 1291

EP - 1298

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 10

ER -

Computing Cumulative Measures of Stiff Markov Chains Using Aggregation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this