EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, VOL.165, NO.3, PP.810-825, 2005.

TITLE: Componentwise Bounds for Nearly Completely Decomposable Markov Chains 
Using Stochastic Comparison and Reordering

AUTHORS: Nihal Pekergin, Tugrul Dayar, and Denizhan N. Alparslan

ABSTRACT: This paper presents an improved version of a componentwise 
bounding algorithm for the state probability vector of nearly completely
decomposable Markov chains, and on an application it provides the first 
numerical results with the type of algorithm discussed. The given 
two-level algorithm uses aggregation and stochastic comparison with the 
strong stochastic (st) order. In order to improve accuracy, it employs 
reordering of states and a better componentwise probability bounding 
algorithm given st upper- and lower-bounding probability vectors. Results 
in sparse storage show that there are cases in which the given algorithm 
proves to be useful.

KEY WORDS: Markov processes; Near complete decomposability; Stochastic
comparison; Reorderings; Aggregation.