SMCTools 2006: Tools for Solving Structured Markov Chains

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

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