Pollaczek–Khinchine formula explained

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 (where jobs arrive according to a Poisson process and have general service time distribution). The term is also used to refer to the relationships between the mean queue length and mean waiting/service time in such a model.^[1]

The formula was first published by Felix Pollaczek in 1930^[2] and recast in probabilistic terms by Aleksandr Khinchin^[3] two years later.^{[4] [5]} In ruin theory the formula can be used to compute the probability of ultimate ruin (probability of an insurance company going bankrupt).^[6]

Mean queue length

The formula states that the mean number of customers in system L is given by^[7]

L = \rho + (\rho ^{2} +λ ^{2} \operatorname{Var)/((S)}{ 2 ( 1- \rho)})

where

λ is the arrival rate of the Poisson process1 /\mu is the mean of the service time distribution S\rho =λ /\mu is the utilization

• Var(S) is the variance of the service time distribution S.

For the mean queue length to be finite it is necessary that

\rho < 1 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 \mu , the queuing delay becomes infinite. The variance term enters the expression due to Feller's paradox.^[8]

Mean waiting time

If we write W for the mean time a customer spends in the system, then

W = W' + \mu ^{-1} where W' is the mean waiting time (time spent in the queue waiting for service) and \mu is the service rate. Using Little's law, which states thatL =λ W 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

W = (\rho +λ \mu Var (S))/(2 (\mu -λ )) + \mu ^{-1} . We can write an expression for the mean waiting time as^[9] W' = (L)/(λ) - \mu ^{-1} = (\rho +λ \mu Var (S))/(2 (\mu -λ )) .

Queue length transform

Writing π(z) for the probability-generating function of the number of customers in the queue^[10]

\pi(z) = (( 1- z)( 1- \rho)g( λ ( 1- z)))/(g( λ ( 1- z)) - z)

where g(s) is the Laplace transform of the service time probability density function.^[11]

Waiting time transform

Writing W^*(s) for the Laplace–Stieltjes transform of the waiting time distribution,^[10]

W ^{\ast(s)} = (( 1- \rho)sg(s))/(s -λ ( 1- g(s)))

where again g(s) is the Laplace transform of service time probability density function. nth moments can be obtained by differentiating the transform n times, multiplying by (−1)ⁿ and evaluating at s = 0.

Notes and References

1. Book: S. R. . Asmussen. 10.1007/0-387-21525-5_8 . Random Walks . Applied Probability and Queues . Stochastic Modelling and Applied Probability . 51 . 220–243 . 2003 . 978-0-387-00211-8 .
2. Pollaczek. F.. Felix Pollaczek. 1930. Über eine Aufgabe der Wahrscheinlichkeitstheorie. Mathematische Zeitschrift. 32. 64–100. 10.1007/BF01194620.
3. Khintchine. A. Y. Aleksandr Khinchin. 1932. Mathematical theory of a stationary queue. Matematicheskii Sbornik. 39. 4. 73–84. 2011-07-14.
4. Review: J. W. Cohen, The Single Server Queue. Lajos. Takács. Lajos Takács. Annals of Mathematical Statistics. 42. 6. 1971. 2162–2164. 10.1214/aoms/1177693087. free.
5. Kingman . J. F. C. . John Kingman . The first Erlang century—and the next . . 63 . 3–4 . 2009 . 10.1007/s11134-009-9147-4.
6. Book: Tomasz . Rolski. Hanspeter . Schmidli. Volker . Schmidt. Jozef . Teugels. 10.1002/9780470317044.ch5 . Risk Processes . Stochastic Processes for Insurance & Finance . Wiley Series in Probability and Statistics . 147–204 . 2008 . 9780470317044 .
7. Book: Haigh, John. Probability Models. 192. Springer. 2002. 1-85233-431-2.
8. Some Reflections on the Renewal-Theory Paradox in Queueing Theory. Robert B.. Cooper. Shun-Chen. Niu. Mandyam M.. Srinivasan. Journal of Applied Mathematics and Stochastic Analysis. 11. 3. 1998. 355–368. 2011-07-14.
9. Book: Harrison, Peter G.. Peter G. Harrison. Naresh M.. Patel. Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. 1992. 228. 0-201-54419-9. registration.
10. Book: John N. . Daigle. 10.1007/0-387-22859-4_5 . The Basic M/G/1 Queueing System . Queueing Theory with Applications to Packet Telecommunication . 159–223 . 2005 . 0-387-22857-8 .
11. Peterson . G. D. . Chamberlain . R. D. . 10.1088/0967-1846/3/1/003 . Parallel application performance in a shared resource environment . Distributed Systems Engineering . 3 . 9 . 1996 . free .