Efficient state classification of finite-state Markov chains
Aiguo Xie, Peter A. Beerel · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1998
This paper presents an efficient method for state classification of finite-state Markov chains using binary-decision diagram-based symbolic techniques. The method exploits the fundamental properties of a Markov chain and classifies the state space by iteratively applying reachability analysis. We compare our method with the state-of-the-art technique, which requires the transitive closure of the transition relation of a Markov chain. Experiments in over a dozen synchronous and asynchronous systems and queueing networks demonstrate that our method dramatically reduces the CPU time needed and solves much larger problems because of the reduced memory requirements.