Optimal state-space lumping in Markov chains

Salem Derisavi, H. Hermanns, William H. Sanders

    Research output: Contribution to journalArticleAcademic

    137 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