Optimal state-space lumping in Markov chains

Salem Derisavi; H. Hermanns; William H. Sanders

doi:10.1016/S0020-0190(03)00343-0

Optimal state-space lumping in Markov chains

Salem Derisavi, H. Hermanns, William H. Sanders

Research output: Contribution to journal › Article › Academic

169 Citations (Scopus)

18 Downloads (Pure)

Abstract

We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652–686]) to sort transition weights.

Original language	Undefined
Pages (from-to)	309-315
Journal	Information processing letters
Volume	87
Issue number	6
DOIs	https://doi.org/10.1016/S0020-0190(03)00343-0
Publication status	Published - 2003

Keywords

IR-75030
Splay trees
Lumpability
Computational Complexity
Markov chains
Bisimulation

Access to Document

10.1016/S0020-0190(03)00343-0

Cite this

@article{6f65358b337f4de8a07c4aaf70f58f24,

title = "Optimal state-space lumping in Markov chains",

abstract = "We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652–686]) to sort transition weights.",

keywords = "IR-75030, Splay trees, Lumpability, Computational Complexity, Markov chains, Bisimulation",

author = "Salem Derisavi and H. Hermanns and Sanders, {William H.}",

year = "2003",

doi = "10.1016/S0020-0190(03)00343-0",

language = "Undefined",

volume = "87",

pages = "309--315",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Optimal state-space lumping in Markov chains

AU - Derisavi, Salem

AU - Hermanns, H.

AU - Sanders, William H.

PY - 2003

Y1 - 2003

N2 - We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652–686]) to sort transition weights.

AB - We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652–686]) to sort transition weights.

KW - IR-75030

KW - Splay trees

KW - Lumpability

KW - Computational Complexity

KW - Markov chains

KW - Bisimulation

U2 - 10.1016/S0020-0190(03)00343-0

DO - 10.1016/S0020-0190(03)00343-0

M3 - Article

SN - 0020-0190

VL - 87

SP - 309

EP - 315

JO - Information processing letters

JF - Information processing letters

IS - 6

ER -