THE FOURTEENTH INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES, 18-20 October 1999 TITLE: Reordering Markov Chains and Stochastic Comparison AUTHORS: Tugrul Dayar and Nihal Pekergin ABSTRACT: This paper investigates the effects of reorderings on stochastic comparison of Markov chains (MCs) with the strong stochastic order. The aim is to find orderings that give tighter probability bounds on a state of interest by reordering the states in the chain. Experiments on MCs show that the proposed 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.