SMCTools 2006: Tools for Solving Structured Markov Chains TITLE: Conditional Steady-State Bounds for a Subset of States in Markov Chains AUTHORS: Tugrul Dayar, Nihal Pekergin, and Sana Younes ABSTRACT: The problem of computing bounds on the conditional steady-state probability vector of a subset of states in finite, ergodic discrete-time Markov chains (DTMCs) is considered. An improved algorithm utilizing the strong stochastic (st-)order is given. On standard benchmarks from the literature and other examples, it is shown that the proposed algorithm performs better than the existing one in the strong stochastic sense. Furthermore, in certain cases the conditional steady-state probability vector of the subset under consideration can be obtained exactly. KEY WORDS: Markov chains, conditional steady-state vector, stochastic comparison, strong stochastic order, bounding