Phase-Type Representations in Random Walk and Queueing Problems

Asmussen, Soren

Ann. Probab., Tome 20 (1992) no. 4, p. 772-789 / Harvested from Project Euclid

Résumé

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 $\mathbf{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 $\mathbf{Q} = \psi(\mathbf{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 $\mathbf{Q}$ has the Rouche roots as its set of eigenvalues.

Détail

Publié le : 1992-04-14
Classification:  Random walk,  ladder height distribution,  phase-type distribution,  Wiener-Hopf factorization,  Markov jump process,  nonlinear matrix iteration,  coupling,  uniformization,  PH/G/1 queue,  GI/PH/1 queue,  60J15,  60J05,  60K25