The Algebraic Construction of Phase-Type Distributions

A probability distribution of discrete phase-type must have a rational generating function. We give 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. We also clarify the relation between the classes of continuous and discrete phase-type distributions, and show 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.