Teorema 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 de trabajos ^{[ 2 ]} ) establece que "al llegar a una estación, un trabajo observa el sistema como si estuviera en estado estacionario 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. Una condición necesaria y suficiente para que se satisfaga el teorema de llegada en redes en forma de producto se da en términos de probabilidades de Palm en Boucherie y Dijk, 1997. ^{[ 4 ]} Un resultado similar también se cumple en algunas redes cerradas. Ejemplos de redes en forma de producto donde no se cumple el teorema de llegada incluyen redes reversibles de Kingman ^{[ 4 ] [ 5 ]} y redes con un protocolo de retardo. ^{[ 3 ]}

Mitrani ofrece la intuición de que "El estado del nodo i visto por un trabajo entrante tiene una distribución diferente al 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 ya presentes". ^{[ 6 ]}

Para los procesos de Poisson, la propiedad se conoce a menudo como la propiedad PASTA (Poisson Arrivals See Time Averages) y establece que la probabilidad del estado vista por un observador aleatorio externo es la misma que la probabilidad del estado vista por un cliente que llega. ^{[ 7 ]} La propiedad también se cumple para el caso de un proceso de Poisson doblemente estocástico, donde se permite que el parámetro de tasa varíe según el estado. ^{[ 8 ]}

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

Note that this theorem does not follow from Jackson's theorem, where the steady state in continuous time is considered. Here we are concerned with particular points in time, namely arrival times.^[9] This theorem first published by Sevcik and Mitrani in 1981.^[10]

In a closed Gordon–Newell network with m queues, write ${\displaystyle {\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}}$ for the state of the network. For a customer in transit to state ${\displaystyle i}$, let ${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$ denote the probability that immediately before arrival the customer 'sees' the state of the system to be

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

This probability, ${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$, is the same as the steady state probability for state ${\displaystyle {\mathbf {n} -\mathbf {e} _ {i}}}$ for a network of the same type with one customer less.^[11] It was published independently by Sevcik and Mitrani,^[10] and Reiser and Lavenberg,^[12] where the result was used to develop mean value analysis.