TECHNICAL REPORT BU-CE-0202, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING

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. A thorough analysis of the two-level algorithm from the 
point of view of irreducibility is provided. Results in sparse storage show 
that there are cases in which the given algorithm proves to be useful.