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.