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.