Optimal state-space lumping in Markov chains
We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(m 1g n) time, where n is the number of states and in 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. (C) 2003 Elsevier B.V. All rights reserved.
markov chains splay trees bisimulation computational complexity lumpability