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.