Fórmula de Pollaczek-Khinchine

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , la fórmula de Pollaczek-Khinchine establece una relación entre la longitud de la cola y la distribución del tiempo de servicio de las transformadas de Laplace para una cola M/G/1 (donde los trabajos llegan según un proceso de Poisson y tienen una distribución general del tiempo de servicio). El término también se utiliza para referirse a las relaciones entre la longitud media de la cola y el tiempo medio de espera/servicio en dicho modelo. ^[1]

La fórmula fue publicada por primera vez por Felix Pollaczek en 1930 ^[2] y reformulada en términos probabilísticos por Aleksandr Khinchin ^[3] dos años después. ^{[4] [5]} En la teoría de la ruina, la fórmula se puede utilizar para calcular la probabilidad de ruina final (probabilidad de que una compañía de seguros se declare en quiebra). ^[6]

Longitud media de la cola

La fórmula establece que el número medio de clientes en el sistema L viene dado por ^[7]

${\displaystyle L=\rho +{\frac {\rho ^{2}+\lambda ^{2}\operatorname {Var} (S)}{2(1-\rho )}}}$

dónde

• ${\displaystyle \lambda }$es la tasa de llegada del proceso de Poisson
• ${\displaystyle 1/\mu }$es la media de la distribución del tiempo de servicio S
• ${\displaystyle \rho =\lambda /\mu }$es la utilización
• Var( S ) es la varianza de la distribución del tiempo de servicio S .

Para que la longitud media de la cola sea finita es necesario que, de lo contrario, los trabajos lleguen más rápido de lo que salen de la cola. La "intensidad de tráfico" oscila entre 0 y 1, y es la fracción media de tiempo que el servidor está ocupado. Si la tasa de llegada es mayor o igual que la tasa de servicio , el retraso en la cola se vuelve infinito. El término de varianza entra en la expresión debido a la paradoja de Feller . ^[8] ${\displaystyle \rho <1}$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$

Tiempo medio de espera

Si escribimos W como el tiempo medio que un cliente pasa en el sistema, entonces donde es el tiempo medio de espera (tiempo que pasa en la cola esperando el servicio) y es la tasa de servicio. Usando la ley de Little , que establece que ${\displaystyle W=W'+\mu ^{-1}}$ ${\displaystyle W'}$ ${\displaystyle \mu }$

${\displaystyle L=\lambda W}$

dónde

• L es el número medio de clientes en el sistema.
• ${\displaystyle \lambda }$es la tasa de llegada del proceso de Poisson
• W es el tiempo medio transcurrido en la cola tanto esperando como siendo atendido,

entonces

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

Podemos escribir una expresión para el tiempo medio de espera como ^[9]

${\displaystyle W'={\frac {L}{\lambda }}-\mu ^{-1}={\frac {\rho +\lambda \mu {\text{Var}}(S)}{2(\mu -\lambda )}}.}$

Transformación de la longitud de la cola

Escribiendo π( z ) para la función generadora de probabilidad del número de clientes en la cola ^[10]

${\displaystyle \pi (z)={\frac {(1-z)(1-\rho )g(\lambda (1-z))}{g(\lambda (1-z))-z}}}$

donde g( s ) es la transformada de Laplace de la función de densidad de probabilidad del tiempo de servicio. ^[11]

Transformación del tiempo de espera

Escribiendo W ^* ( s ) para la transformada de Laplace-Stieltjes de la distribución del tiempo de espera, ^[10]

${\displaystyle W^{\ast }(s)={\frac {(1-\rho )sg(s)}{s-\lambda (1-g(s))}}}$

donde nuevamente g( s ) es la transformada de Laplace de la función de densidad de probabilidad del tiempo de servicio. Los momentos n- ésimos se pueden obtener diferenciando la transformada n veces, multiplicando por (−1) ⁿ y evaluando en s  = 0.

Referencias

1. Asmussen, SR (2003). "Paseos aleatorios". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol. 51. págs. 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). "Teoría matemática de una cola estacionaria". Matematicheskii Sbornik . 39 (4): 73–84 . Consultado el 14 de julio de 2011 .
4. Takács, Lajos (1971). "Revisión: JW Cohen, The Single Server Queue". Anales de estadística matemática . 42 (6): 2162–2164. doi : 10.1214/aoms/1177693087 .
5. Kingman, JFC (2009). "El primer siglo de Erlang y el próximo". Queueing Systems . 63 : 3–4. doi :10.1007/s11134-009-9147-4.
6. Rolski, Tomasz; Schmidli, Hanspeter; Schmidt, Volker; Teugels, Jozef (2008). "Procesos de riesgo". Procesos estocásticos para seguros y finanzas . Serie Wiley en probabilidad y estadística. págs. 147–204. doi :10.1002/9780470317044.ch5. ISBN 9780470317044.
7. Haigh, John (2002). Modelos de probabilidad . Springer. pág. 192. ISBN. 1-85233-431-2.
8. Cooper, Robert B.; Niu, Shun-Chen; Srinivasan, Mandyam M. (1998). "Algunas reflexiones sobre la paradoja de la teoría de renovación en la teoría de colas" (PDF) . Journal of Applied Mathematics and Stochastic Analysis . 11 (3): 355–368 . Consultado el 14 de julio de 2011 .
9. Harrison, Peter G. ; Patel, Naresh M. (1992). Modelado del rendimiento de redes de comunicación y arquitecturas informáticas . Addison-Wesley. pág. 228. ISBN 0-201-54419-9.
10. Daigle, John N. (2005). "El sistema básico de colas M/G/1". Teoría de colas con aplicaciones a la telecomunicación por paquetes . págs. 159–223. doi :10.1007/0-387-22859-4_5. ISBN 0-387-22857-8.
11. Peterson, GD; Chamberlain, RD (1996). "Rendimiento de aplicaciones paralelas en un entorno de recursos compartidos". Ingeniería de sistemas distribuidos . 3 : 9. doi : 10.1088/0967-1846/3/1/003 .