PHASE-TYPE REPRESENTATIONS IN RANDOM-WALK AND QUEUING-PROBLEMS

The distributions of random walk quantities like ascending ladder heights and the maximum are shown to be phase-type provided that the generic random walk increment X has difference structure X = U - T with U phase-type, or the one-sided assumption of X+ being phase-type is imposed. As a corollary, it follows that the stationary waiting time in a GI/PH/1 queue with phase-type service times is again phase-type. The phase-type representations are characterized in terms of the intensity matrix Q of a certain Markov jump process associated with the random walk. From an algorithmic point of view, the fundamental step is the iterative solution of a fix-point problem Q = phi(Q), and using a coupling argument it is shown that the iteration typically converges geometrically fast. Also, a variant of the classical approach based upon Rouche's theorem and root-finding in the complex plane is derived, and the relation between the approaches is shown to be that Q has the Rouche roots as its set of eigenvalues.