TECHNICAL REPORT BU-CEIS-9505, BILKENT UNIVERSITY, DEPARTMENT OF COMPUTER ENGINEERING AND INFORMATION SCIENCE TITLE: Exploring States of Sparse, Large Markov Chains AUTHORS: Tugrul Dayar and William J. Stewart ABSTRACT: Dynamic state exploration is an effective technique to explore states of sparse, large Markov chains having highly unbalanced stationary probabilities and to compute related performance measures for them. States of interest are explored starting from a particular state until a predetermined stopping criterion is met. In this paper, the dynamic state exploration idea is extended to the case where more than one starting state is considered simultaneously. This approach easily lends itself to parallel implementation and reduces the number of operations to be carried out for each starting state. Furthermore, it is shown that this approach gives quite an accurate feeling for the nature of the states without having to solve the complete Markov chain. Experiments are carried out on a Markov chain arising from an Asynchronous Transfer Mode (ATM) traffic queue.