A probability distribution of discrete phase-type must have a rational generating function. The paper gives an algorithm that constructs, from a given rational function G(z), a Markov chain whose absorption-time distribution has G(z) as generating function. The algorithm, which is based on an automata-theoretic algorithm of Soittola, may be applied to any G(z) that satisfies the conditions on discrete phase-type generating functions discovered by O’Cinneide. So it provides an alternative, algebraic proof of O’Cinneide’s characterisation of discrete phase-type distributions. The paper also clarifies the relation between the classes of continuous and discrete phase-type distributions, and shows that O’Cinneide’s characterisation of continuous phase-type distributions is a corollary of his discrete characterisation. In conjunction with our discrete-time algorithm, this engenders an algorithm for constructing a Markov process representation for any distribution of continuous phase-type.
