Pollaczek–Khinchine formula


In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula states a relationship between the queue length and service time distribution Laplace transforms for an M/G/1 queue. The term is also used to refer to the relationships between the mean queue length and mean waiting/service time in such a model.
The formula was first published by Felix Pollaczek in 1930 and recast in probabilistic terms by Aleksandr Khinchin two years later. In ruin theory the formula can be used to compute the probability of ultimate ruin.

Mean queue length

The formula states that the mean number of customers in system L is given by
where
For the mean queue length to be finite it is necessary that as otherwise jobs arrive faster than they leave the queue. "Traffic intensity," ranges between 0 and 1, and is the mean fraction of time that the server is busy. If the arrival rate is greater than or equal to the service rate, the queuing delay becomes infinite. The variance term enters the expression due to Feller's paradox.

Mean waiting time

If we write W for the mean time a customer spends in the system, then where is the mean waiting time and is the service rate. Using Little's law, which states that
where
  • L is the mean number of customers in system
  • is the arrival rate of the Poisson process
  • W is the mean time spent at the queue both waiting and being serviced,
so
We can write an expression for the mean waiting time as

Queue length transform

Writing π for the probability-generating function of the number of customers in the queue
where g is the Laplace transform of the service time probability density function.

Waiting time transform

Writing W* for the Laplace–Stieltjes transform of the waiting time distribution,
where again g is the Laplace transform of service time probability density function. Each nth moment can be obtained by differentiating the transform n times, multiplying by n and evaluating at s = 0. If one multiplies this W* by g, then one receives the Laplace–Stieltjes transform for the distribution of the sojourn time.