SMCTools 2006: Tools for Solving Structured Markov Chains 

TITLE: Conditional Steady-State Bounds for a Subset of States in 
       Markov Chains

AUTHOR: 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