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.