Optimal state-space lumping in Markov chains

Salem Derisavi, Holger Hermanns, William H. Sanders

Research output: Contribution to journalArticlepeer-review


A study on optimal state-space lumping in Markov chains is presented. It is proved that the optimal lumping quotient of a finite Markov chain can be constructed in O(m lg n) time, where n is the number of states and m is the number of transitions. The proof relies on the use of splay trees to sort transition weights.

Original languageEnglish (US)
Pages (from-to)309-315
Number of pages7
JournalInformation Processing Letters
Issue number6
StatePublished - Sep 30 2003


  • Bisimulation
  • Computational complexity
  • Lumpability
  • Markov chains
  • Splay trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Optimal state-space lumping in Markov chains'. Together they form a unique fingerprint.

Cite this