Teorema de llegada

Teorema de la teoría de colas sobre el comportamiento instantáneo en los tiempos de llegada

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el teorema de llegada ^[1] (también conocido como propiedad del observador aleatorio , ROP o propiedad del observador del trabajo ^[2] ) establece que "al llegar a una estación, un trabajo observa el sistema como si estuviera en estado estable en un instante arbitrario para el sistema sin ese trabajo". ^[3]

El teorema de llegada siempre se cumple en redes abiertas en forma de producto con colas ilimitadas en cada nodo, pero también se cumple en redes más generales. En Boucherie & Dijk, 1997, se da una condición necesaria y suficiente para que se cumpla el teorema de llegada en redes en forma de producto en términos de probabilidades de Palm ^{. [4]} Un resultado similar también se cumple en algunas redes cerradas. Entre los ejemplos de redes en forma de producto donde el teorema de llegada no se cumple se incluyen las redes Kingman reversibles ^{[4] [5]} y las redes con un protocolo de retardo. ^[3]

Mitrani ofrece la intuición de que "el estado del nodo i tal como lo ve un trabajo entrante tiene una distribución diferente del estado visto por un observador aleatorio. Por ejemplo, un trabajo entrante nunca puede ver todos los ' k trabajos presentes en el nodo i , porque él mismo no puede estar entre los trabajos que ya están presentes". ^[6]

Teorema de llegadas gobernadas por un proceso de Poisson

En el caso de los procesos de Poisson, la propiedad se denomina a menudo propiedad PASTA (Poisson Arrivals See Time Averages) y establece que la probabilidad del estado tal como lo ve un observador aleatorio externo es la misma que la probabilidad del estado visto por un cliente que llega. ^[7] La ​​propiedad también es válida para el caso de un proceso de Poisson doblemente estocástico en el que se permite que el parámetro de velocidad varíe según el estado. ^[8]

Teorema de redes de Jackson

En una red Jackson abierta con m colas, escriba para el estado de la red. Suponga que es la probabilidad de equilibrio de que la red esté en el estado . Entonces, la probabilidad de que la red esté en el estado inmediatamente antes de una llegada a cualquier nodo también es . ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\textstyle \pi (\mathbf {n} )}$ ${\textstyle \mathbf {n} }$ ${\textstyle \mathbf {n} }$ ${\textstyle \pi (\mathbf {n} )}$

Obsérvese que este teorema no se deduce del teorema de Jackson , donde se considera el estado estacionario en tiempo continuo. Aquí nos ocupamos de puntos particulares en el tiempo, es decir, tiempos de llegada. ^[9] Este teorema fue publicado por primera vez por Sevcik y Mitrani en 1981. ^[10]

Teorema de las redes de Gordon-Newell

En una red Gordon-Newell cerrada con m colas, escriba para el estado de la red. Para un cliente en tránsito al estado , denote la probabilidad de que inmediatamente antes de la llegada el cliente "vea" que el estado del sistema es ${\displaystyle {\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}}$ ${\displaystyle i}$ ${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$

${\displaystyle \mathbf {n} -\mathbf {e} _{i}=(n_{1},n_{2},\ldots ,n_{i}-1,\ldots ,n_{m}).}$

Esta probabilidad, , es la misma que la probabilidad de estado estable para el estado de una red del mismo tipo con un cliente menos . ^[11] Fue publicada de forma independiente por Sevcik y Mitrani, ^[10] y Reiser y Lavenberg, ^[12] donde el resultado se utilizó para desarrollar un análisis de valor medio . ${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$ ${\displaystyle {\mathbf {n} -\mathbf {e} _{i}}}$

Notas

1. Asmussen, Søren (2003). "Redes de colas e insensibilidad". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol. 51. págs. 114–136. doi :10.1007/0-387-21525-5_4. ISBN 978-0-387-00211-8.
2. El-Taha, Muhammad (1999). Análisis de rutas de muestra de sistemas de colas . Springer. pág. 94. ISBN 0-7923-8210-2.
3. Van Dijk, NM (1993). "Sobre el teorema de llegada para redes de comunicación". Redes informáticas y sistemas RDSI . 25 (10): 1135–2013. doi :10.1016/0169-7552(93)90073-D.
4. Boucherie, RJ; Van Dijk, NM (1997). "Sobre el teorema de llegada para redes de colas de forma de producto con bloqueo". Evaluación del rendimiento . 29 (3): 155. doi :10.1016/S0166-5316(96)00045-4.
5. Kingman, JFC (1969). "Procesos de población de Markov". Revista de probabilidad aplicada . 6 (1). Applied Probability Trust: 1–18. doi :10.2307/3212273. JSTOR  3212273.
6. Mitrani, Isi (1987). Modelado de sistemas informáticos y de comunicación. CUP. p. 114. ISBN 0521314224.
7. Wolff, RW (1982). "Las llegadas de Poisson ven los promedios de tiempo". Investigación de operaciones . 30 (2): 223–231. doi :10.1287/opre.30.2.223.
8. Van Doorn, EA; Regterschot, GJK (1988). «PASTA condicional» (PDF) . Cartas de investigación operativa . 7 (5): 229. doi :10.1016/0167-6377(88)90036-3.
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. Sevcik, KC; Mitrani, I. (1981). "La distribución de estados de red de colas en instantes de entrada y salida". Revista de la ACM . 28 (2): 358. doi : 10.1145/322248.322257 .
11. Breuer, L.; Baum, Dave (2005). "Redes de colas markovianas". Introducción a la teoría de colas y métodos de análisis matriciales . págs. 63-61. doi :10.1007/1-4020-3631-0_5. ISBN 1-4020-3630-2.
12. Reiser, M.; Lavenberg, SS (1980). "Análisis de valor medio de redes de colas multicadena cerradas". Revista de la ACM . 27 (2): 313. doi : 10.1145/322186.322195 .