Probability in the Engineering and Informational Sciences

Research Article

A SUCCESSIVE LUMPING PROCEDURE FOR A CLASS OF MARKOV CHAINS

Michael N. Katehakisa1 and Laurens C. Smita2

a1 Department of Management Science and Information Systems, Rutgers Business School, Newark and New Brunswick, Newark, NJ 07210 E-mail: mnk@rutgers.edu

a2 Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, 2333 CA, The Netherlands E-mail: lsmit@math.leidenuniv.nl

Abstract

A class of Markov chains we call successively lumbaple is specified for which it is shown that the stationary probabilities can be obtained by successively computing the stationary probabilities of a propitiously constructed sequence of Markov chains. Each of the latter chains has a(typically much) smaller state space and this yields significant computational improvements. We discuss how the results for discrete time Markov chains extend to semi-Markov processes and continuous time Markov processes. Finally, we will study applications of successively lumbaple Markov chains to classical reliability and queueing models.