Equivalent Markov-Renewal Processes.
Abstract
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 umimportant 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, periodic and transient MRP's. These results are applied to problems concerning flows in queueing networks. It is shown that several well known 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1979
- Accession Number
- ADA080836
Entities
People
- Burton Simon
Organizations
- Virginia Tech