stringtranslate.com

Teorema de Burke

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el teorema de Burke (a veces el teorema de salida de Burke [1] ) es un teorema (enunciado y demostrado por Paul J. Burke mientras trabajaba en Bell Telephone Laboratories ) que afirma que, para la cola M/M/1 , la cola M/M/c o la cola M/M/∞ en estado estable con llegadas es un proceso de Poisson con parámetro de velocidad λ:

  1. El proceso de salida es un proceso de Poisson con parámetro de velocidad λ.
  2. En el momento t el número de clientes en la cola es independiente del proceso de salida anterior al momento  t .

Prueba

Burke publicó por primera vez este teorema junto con una prueba en 1956. [2] El teorema fue anticipado pero no demostrado por O'Brien (1954) y Morse (1955). [3] [4] [5] Una segunda prueba del teorema se desprende de un resultado más general publicado por Reich. [6] La prueba ofrecida por Burke muestra que los intervalos de tiempo entre salidas sucesivas se distribuyen de forma independiente y exponencial con un parámetro igual al parámetro de tasa de llegada, del que se desprende el resultado.

Rastro con instantes de salida/llegada resaltados en el proceso de tiempo adelante/atrás.

Una prueba alternativa es posible considerando el proceso inverso y notando que la cola M/M/1 es un proceso estocástico reversible. [7] Considere la figura. Por el criterio de Kolmogorov para reversibilidad, cualquier proceso de nacimiento-muerte es una cadena de Markov reversible . Nótese que los instantes de llegada en la cadena de Markov hacia adelante son los instantes de salida de la cadena de Markov hacia atrás. Por lo tanto, el proceso de salida es un proceso de Poisson de tasa λ. Además, en el proceso hacia adelante, la llegada en el tiempo t es independiente del número de clientes después de t. Por lo tanto, en el proceso inverso, el número de clientes en la cola es independiente del proceso de salida antes del tiempo  t .

Esta prueba podría ser contra-intuitiva, en el sentido de que el proceso de salida de un proceso de nacimiento-muerte es independiente del servicio ofrecido.

Resultados y extensiones relacionados

El teorema se puede generalizar para "sólo unos pocos casos", pero sigue siendo válido para colas M/M/c y colas Geom/Geom/1. [7]

Se cree que el teorema de Burke no se extiende a las colas alimentadas por un proceso de llegada markoviano (MAP) y se conjetura que el proceso de salida de una cola MAP/M/1 es un MAP solo si la cola es una cola M/M/1. [8]

J. Michael Harrison demostró un teorema análogo para la cola browniana . [3] [9]

Referencias

  1. ^ Walrand, J. (1983). "Una mirada probabilística a las redes de colas cuasi-reversibles". IEEE Transactions on Information Theory . 29 (6): 825–831. doi :10.1109/TIT.1983.1056762. S2CID  216943.
  2. ^ Burke, PJ (1956). "La salida de un sistema de colas". Investigación de operaciones . 4 (6): 699–704. doi :10.1287/opre.4.6.699. S2CID  55089958.
  3. ^ ab O'Connell, N.; Yor, M. (diciembre de 2001). "Análogos brownianos del teorema de Burke". Procesos estocásticos y sus aplicaciones . 96 (2): 285–298. doi : 10.1016/S0304-4149(01)00119-3 .
  4. ^ O'Brien, GG (septiembre de 1954). "La solución de algunos problemas de colas". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 2 (3): 133–142. doi :10.1137/0102010. JSTOR  2098899.
  5. ^ Morse, PM (agosto de 1955). "Propiedades estocásticas de las líneas de espera". Revista de la Sociedad de Investigación de Operaciones de Estados Unidos . 3 (3): 255–261. doi :10.1287/opre.3.3.255. JSTOR  166559.
  6. ^ Reich, Edgar (1957). "Tiempos de espera cuando las colas están en tándem". Anales de estadística matemática . 28 (3): 768–773. doi : 10.1214/aoms/1177706889 .
  7. ^ ab Hui, JY (1990). "Colas para redes de paquetes de múltiples etapas". Teoría de conmutación y tráfico para redes de banda ancha integradas . Serie internacional Kluwer en ingeniería y ciencias de la computación. Vol. 91. págs. 313–341. doi :10.1007/978-1-4615-3264-4_11. ISBN 978-1-4613-6436-8.
  8. ^ Bean, Nigel; Green, David; Taylor, Peter (1998). "El proceso de salida de una cola MMPP/M/1". Journal of Applied Probability . 35 (4): 998. CiteSeerX 10.1.1.44.8263 . doi :10.1239/jap/1032438394. S2CID  122137199. 
  9. ^ Harrison, J. Michael (1985). Movimiento browniano y sistemas de flujo estocástico (PDF) . Nueva York: Wiley. Archivado desde el original (PDF) el 14 de abril de 2012. Consultado el 1 de diciembre de 2011 .