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. Transformadas de Laplace para una cola M/G/1 (donde los trabajos llegan según un proceso de Poisson y tienen distribución del tiempo de servicios generales). 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 quiebre). ^[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 del 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 a 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 para el tiempo medio que pasa un cliente en el sistema, entonces ¿dónde está el tiempo medio de espera (tiempo pasado en la cola esperando el servicio) y es la tarifa del servicio? Utilizando 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 esperando y 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 longitud de 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 n- ésimos momentos 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 . Modelización estocástica 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, AY (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, la cola de servidor único". 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 siguiente". Sistemas de colas . 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 . Saltador. pag. 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 la renovación en la teoría de las colas" (PDF) . Revista de Matemáticas Aplicadas y Análisis Estocástico . 11 (3): 355–368 . Consultado el 14 de julio de 2011 .
9. Harrison, Peter G .; Patel, Naresh M. (1992). Modelado de rendimiento de redes de comunicación y arquitecturas informáticas . Addison-Wesley. pag. 228.ISBN​ 0-201-54419-9.
10. Daigle, John N. (2005). "El sistema de colas básico M/G/1". Teoría de colas con aplicaciones a las telecomunicaciones 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 .