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.