System Analysis of Semi-Markov Processes

Abstract

Flow graph analysis has proved a valuable approach to the study of probabilistic systems. This paper extends the analytic procedures to semi-Markov processes, Markov processes whose transition times can also be arbitrary random variables. First we present the basic theory of the semi-Markov process. We derive expressions for the interval transition probabilities, the probabilities that the system will be in each state after the passage of a time interval of length t, and find the limit of these probabilities when t is large. Then we develop the flow graph interpretation of these relations. We consider the special cases of counting transitions, transient processes, and first passage times. We investigate the effect on interval transition probabilities of starting the process in different ways, including choosing a time at random to begin observation of the process. We find that results are often most conveniently expressed by the matrix flow graph for the process.