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.