Optimal state-space lumping in Markov chains

Salem Derisavi, H. Hermanns, William H. Sanders

    Research output: Contribution to journalArticleAcademic

    132 Citations (Scopus)

    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 languageUndefined
    Pages (from-to)309-315
    JournalInformation processing letters
    Volume87
    Issue number6
    DOIs
    Publication statusPublished - 2003

    Keywords

    • IR-75030
    • Splay trees
    • Lumpability
    • Computational Complexity
    • Markov chains
    • Bisimulation

    Cite this

    Derisavi, Salem ; Hermanns, H. ; Sanders, William H. / Optimal state-space lumping in Markov chains. In: Information processing letters. 2003 ; Vol. 87, No. 6. pp. 309-315.
    @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",

    }

    Derisavi, S, Hermanns, H & Sanders, WH 2003, 'Optimal state-space lumping in Markov chains', Information processing letters, vol. 87, no. 6, pp. 309-315. https://doi.org/10.1016/S0020-0190(03)00343-0

    Optimal state-space lumping in Markov chains. / Derisavi, Salem; Hermanns, H.; Sanders, William H.

    In: Information processing letters, Vol. 87, No. 6, 2003, p. 309-315.

    Research output: Contribution to journalArticleAcademic

    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

    VL - 87

    SP - 309

    EP - 315

    JO - Information processing letters

    JF - Information processing letters

    SN - 0020-0190

    IS - 6

    ER -