Equivalent Markov-Renewal Processes.
Burton Simon · Defense Technical Information Center (DTIC) · 1979
The concept of strong and weak lumpability between Markov chains was introduced by Burke and Rosenblatt in 1958. In 1969 Serfozo showed that the concept of lumpability extends easily to Markov-renewal processes (MRP's). These concepts are apparently considered unimportant by the masses since there has been very little reference to them in the literature since 1972. The reason for the lack of interest is probably that the conditions for strong lumpability are too strong to be useful and nobody has ever considered the important special case of weak lumpability from a MRP to a renewal process. What is shown here is that in an appropriate modified form, these concepts are important in both application and in the foundational study of MRP's. Equivalence and collapsibility between MRP's are defined, and necessary, sufficient, and necessary and sufficient conditions are given for them. It is shown that equivalence, collapsibility, weak lumpability and strong lumpability are morphisms between MRP's, and their relations to one another are examined. Equivalence between a MRP and a renewal process is examined in detail. Specific results are obtained for irreducible, reducible, periodic and transient MRP's. These results are applied to problems concerning flows in queueing networks. It is shown that several well known results in queueing theory are examples of equivalence (for instance Burke's Theorem). New and simpler proofs are given for them. Some questions, previously unresolved, are answered using the techniques developed here; most notably the question of when the input process to the M/M/1 queue with instantaneous Bernoulli feedback is renewal. Convolutions of MRP's are examined, and conditions are given for equivalence to be preserved under convolution. It is also shown that an important class of Markov-renewal equations can be simplified if the underlying MRP is equivalent to the renewal process. Finally, it is shown that the ideas developed here can be extended to MRP's on general state spaces. The definitions of equivalence, collapsibility, weak lumpability and strong lumpability are given in the general setting. Examples from queueing theory that would make use of the generalized results are given.