SEMINAR

ABSTRACT

Denizhan N. Alparslan

M.S. in Computer Engineering

Supervisor: Assist. Prof.Dr. Tuðrul Dayar

July 12, 2000

STOCHASTIC COMPARISON ON NEARLY COMPLETELY DECOMPOSABLE MARKOV CHAINS

This thesis presents an improved version of a componentwise bounding algorithm for the steady state probability vector of nearly completely decomposable Markov chains. The given two-level algorithm uses aggregation, stochastic comparison with the strong stochastic (st) order, and reordering of the states. It employs a new st-monotone lower-bounding matrix construction algorithm to improve run-time, reordering and a better componentwise probability bounding algorithm given st upper- and lower-bounding probability vectors to improve accuracy. A thorough analysis of the algorithm from the point of view of irreducibility is provided. The bounding algorithm is implemented in sparse storage and its implementation details are given. Numerical results on a real-life application of wireless Asynchronous Transfer Mode network show that there are cases in which the given algorithm proves to be useful in computing bounds on the performance measures of the system. An improvement in the algorithm that must be considered to obtain better bounds on performance measures is also presented at the end.

Keywords: Markov chains, near complete decomposability, stochastic comparison, st-order, reorderings, aggregation

The Seminar will be on June 12, 2000, at 10:40

in EA502