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

• 成果类型: Article
• 署名作者: ASMUSSEN, S
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1176989805
• 发表日期: 1992
• 页码: 772-789
• 关键词: matrix

摘要

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.