Approximating M/G/1 Waiting Time Tail Probabilities

Abstract

We propose a new approximation formula for the waiting time tail probability of the M/G/1 queue with FIFO discipline and unlimited waiting space. The aim is to address the difficulty of obtaining good estimates when the tail probability has non-exponential asymptotics. We show that the waiting time tail probability can be expressed in terms of the waiting time tail probability of a notional M/G/1 queue with truncated service time distribution plus the tail probability of an extreme order statistic. The Cramér–Lundberg approximation is applied to approximate the tail probability of the notional queue. In essence, our technique extends the applicability of the Cramér–Lundberg approximation to cases where the standard Lundberg condition does not hold. We propose a simple moment-based technique for estimating the parameters of the approximation; numerical results demonstrate that our approximation can yield very good estimates over the whole range of the argument.     

A computational algorithm for the loss probability in the M/G/1+PH queue

This article develops a computational algorithm for the loss probability in the stationary M/G/1 queue with impatient customers whose impatience times follow a phase-type distribution (M/G/1+PH). The algorithm outputs the loss probability, along with an upper-bound of its numerical error due to truncation, and it is readily applicable to the M/D/1+PH, M/PH/1+PH, and M/Pareto/1+PH queues.     

The covariance of the number of renewals in a fixed time and the ensuing excess life

The covariance of the number of renewals in a fixed time N ^t and the ensuing excess life time Y ^t is derived using matrix-analytic methods for the stationary PH-renewal process. Specific results for the Erlang and hyperexponential processes are provided to illustrate the ease of computation. Properties concerning the sign and the behavior of the covariance as t→∞ are provided throughout. Parameter estimation for renewal processes which cannot be fully observed serves as the motivation for our derivations. These statistical applications as well as links to estimation for service time distributions in queues shed light on the type of problems for which the covariance is useful.