Calculation of the GI/G/1 waiting-time distribution and its cumulants from Pollaczek's formulas

Abstract

AbstractThe steady-state waiting time in a stable GI/G/1 queue is equivalent to the maximum of ageneral random walk with negative drift. Thus, the distribution of the steady-state waiting time inthe GI/G/1 queue is characterized by Spitzer’s (1956) formula. However, earlier, Pollaczek(1952) derived an equivalent contour-integral expression for the Laplace transform of the GI/G/1steady-state waiting time. Since Spitzer’s formula is easier to understand probabilistically, it isbetter known today, but it is not so easy to apply directly except in special cases. In contrast, weshow that it is easy to compute the GI/G/1 waiting-time distribution and its cumulants (and thusits moments) from Pollaczek’s formulas. For the waiting-time tail probabilities, we usenumerical transform inversion, numerically integrating the Pollaczek contour integral to obtainthe transform values. For the cumulants and the probability of having to wait, we directlyintegrate the Pollazcek contour integrals numerically. The resulting algorithm is evidently thefirst for a GI/G/1 queue in which neither the transform of the interarrival-time distribution nor thetransform of the service-time transform distribution need be rational. The algorithm can even beapplied to long-tail distributions, i.e., distributions with some infinite moments. To treat thesedistributions, we approximate them by suitable exponentially-damped versions of thesedistributions. Overall, the algorithm is remarkably simple compared to alternative algorithmsrequiring more structure.key words:Fe ´ lix Pollaczek, queueing theory, computational probability, GI/G/1 queue, waitingtime distribution, tail probabilities, random walk, Spitzer’s formula, numerical transforminversion, numerical integration, contour integrals.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 42 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.