Numerical Solution of Markov Chains (NSMC'99)

TITLE: Stochastic Comparison, Reorderings, and Nearly Completely 
Decomposable Markov Chains

AUTHORS: Tugrul Dayar and Nihal Pekergin

ABSTRACT: This paper investigates the effects of reorderings on stochastic
comparison of Markov chains with the strong stochastic order. The heuristic
of minimizing the total perturbation in the last column of the reordered
matrix is used to devise an algorithm to find probability bounds on a given
state in nearly completely decomposable (NCD) Markov chains. The algorithm
permutes the state of interest and the NCD partition to which it belongs to
be the last and aggregates each remaining NCD partition so as to reduce the
size of the state space. The approach is to find an ordering that gives
tight probability bounds by reordering the states in the last NCD partition
with respect to the state of interest and the aggregated NCD partitions
with respect to the last NCD partition. Exhaustive experiments on two 
well-known NCD Markov chains show that the heuristic algorithm fares very 
well and is able to find the orderings giving the tightest bounds for most
states. Whenever, this is not possible, the bounds obtained with the
resulting orderings are acceptably close to the best bounds computed with
the strong stochastic order. A measure useful in forecasting the quality of
bounds obtained with the described approach is also given.