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 (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 = ρ + ρ 2 + λ 2 Var ⁡ ( S ) 2 ( 1 − ρ ) {\displaystyle L=\rho +{\frac {\rho ^{2}+\lambda ^{2}\operatorname {Var} (S)}{2(1-\rho )}}}

where

  • λ {\displaystyle \lambda } is the arrival rate of the Poisson process
  • 1 / μ {\displaystyle 1/\mu } is the mean of the service time distribution S
  • ρ = λ / μ {\displaystyle \rho =\lambda /\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 ρ < 1 {\displaystyle \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 λ {\displaystyle \lambda } is greater than or equal to the service rate μ {\displaystyle \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 ′ + μ − 1 {\displaystyle W=W'+\mu ^{-1}} where W ′ {\displaystyle W'} is the mean waiting time (time spent in the queue waiting for service) and μ {\displaystyle \mu } is the service rate. Using Little's law, which states that

L = λ W {\displaystyle L=\lambda W}

where

  • L is the mean number of customers in system
  • λ {\displaystyle \lambda } is the arrival rate of the Poisson process
  • W is the mean time spent at the queue both waiting and being serviced,

so

W = ρ + λ μ Var ( S ) 2 ( μ − λ ) + μ − 1 . {\displaystyle W={\frac {\rho +\lambda \mu {\text{Var}}(S)}{2(\mu -\lambda )}}+\mu ^{-1}.}

We can write an expression for the mean waiting time as[9]

W ′ = L λ − μ − 1 = ρ + λ μ Var ( S ) 2 ( μ − λ ) . {\displaystyle W'={\frac {L}{\lambda }}-\mu ^{-1}={\frac {\rho +\lambda \mu {\text{Var}}(S)}{2(\mu -\lambda )}}.}

Queue length transform

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

π ( z ) = ( 1 − z ) ( 1 − ρ ) g ( λ ( 1 − z ) ) g ( λ ( 1 − z ) ) − z {\displaystyle \pi (z)={\frac {(1-z)(1-\rho )g(\lambda (1-z))}{g(\lambda (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 ∗ ( s ) = ( 1 − ρ ) s g ( s ) s − λ ( 1 − g ( s ) ) {\displaystyle W^{\ast }(s)={\frac {(1-\rho )sg(s)}{s-\lambda (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)n and evaluating at s = 0.

References

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