16.12: Cadenas de Colas de Tiempo Discreto

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

Teoría Básica

Introducción

En un modelo de cola, los clientes llegan a una estación para recibir servicio. Como siempre, los términos son genéricos; aquí hay algunos ejemplos típicos:

• Los clientes son personas y la estación de servicio es una tienda.
• Los clientes son solicitudes de archivo y la estación de servicio es un servidor web.
• Los clientes son paquetes y la estación de servicio es una instalación de procesamiento.

Figura\(\PageIndex{1}\): Diez clientes y un servidor

Los modelos de colas pueden ser bastante complejos, dependiendo de factores como la distribución de probabilidad que gobierna la llegada de los clientes, la distribución de probabilidad que gobierna el servicio de los clientes, el número de servidores y el comportamiento de los clientes cuando todos los servidores están ocupados. En efecto, la teoría de colas tiene su propio léxico para indicar algunos de estos factores. En esta sección, estudiaremos uno de los modelos de cola de tiempo discreto más simples y discretos. Sin embargo, como veremos, esta cadena de tiempo discreta está incrustada en un proceso de cola de tiempo continuo mucho más realista conocido como la cola M/G/1. En un sentido general, el interés principal en cualquier modelo de colas es el número de clientes en el sistema en función del tiempo, y en particular, si los servidores pueden manejar adecuadamente el flujo de clientes.

Nuestros supuestos principales son los siguientes:

1. Si la cola está vacía en un momento dado, entonces un número aleatorio de nuevos clientes llegan a la próxima vez.
2. Si la cola no está vacía en un momento dado, entonces se atiende a un cliente y un número aleatorio de nuevos clientes llegan a la próxima vez.
3. El número de clientes que llegan a cada periodo de tiempo forman una secuencia independiente, distribuida de manera idéntica.

Por lo tanto, vamos a\( X_n \) denotar el número de clientes en el sistema en el momento\( n \in \N \), y dejar\( U_n \) denotar el número de nuevos clientes que llegan a tiempo\( n \in \N_+ \). Entonces\( \bs{U} = (U_1, U_2, \ldots) \) es una secuencia de variables aleatorias independientes, con función de densidad de probabilidad común\( f \) en\( \N \), y\[ X_{n+1} = \begin{cases} U_{n+1}, & X_n = 0 \\ (X_n - 1) + U_{n+1}, & X_n \gt 0 \end{cases}, \quad n \in \N \]

\( \bs{X} = (X_0, X_1, X_2, \ldots) \)es una cadena de Markov de tiempo discreto con espacio de estado\( \N \) y matriz de probabilidad de transición\( P \) dada por\ begin {align} P (0, y) & = f (y),\ quad y\ in\ N\\ P (x, y) & = f (y - x + 1),\ quad x\ in\ N_+,\; y\ in\ {x - 1, x, x + 1,\ ldots\} end {align} La cadena\( \bs{X} \) es la cadena de colas con distribución de llegada definida por\( f \).

Prueba

La propiedad de Markov y la forma de la matriz de transición se derivan de la construcción del proceso estatal\( \bs{X} \) en términos de la secuencia IID\( \bs{U} \). Comenzando en el estado 0 (una cola vacía), un número aleatorio de nuevos clientes llegan a la siguiente unidad de tiempo, regida por el PDF\( f \). De ahí que la probabilidad de pasar del estado 0 al estado\( y \) en un solo paso es\( f(y) \). Comenzando en estado\( x \in \N_+ \), un cliente es atendido y un número aleatorio de nuevos clientes llegan por la siguiente unidad de tiempo, nuevamente regidos por el PDF\( f \). De ahí que sea la probabilidad de ir de estado\( x \)\( y \in \{x - 1, x, x + 1, \ldots\} \) en estado\( f[y - (x - 1)] \).

Recurrencia y fugacidad

A partir de ahora vamos a asumir que\( f(0) \gt 0 \) y\( f(0) + f(1) \lt 1 \). Así, en cada unidad de tiempo, es posible que no lleguen nuevos clientes o que lleguen al menos 2 nuevos clientes. También, dejamos\( m \) denotar la media de la distribución de llegada, de manera que\[ m = \sum_{x = 0}^\infty x f(x) \] así\( m \) es el número promedio de nuevos clientes que llegan durante un periodo de tiempo.

La cadena\( \bs{X} \) es irreducible y aperiódica.

Prueba

En un estado positivo, la cadena puede mover al menos una unidad hacia la derecha y puede mover una unidad hacia la izquierda en el siguiente paso. Desde el estado 0, la cadena puede mover dos o más unidades hacia la derecha o puede permanecer en 0 en el siguiente paso. Así, cada estado conduce a cada otro estado por lo que la cadena es irreducible. Dado que 0 lleva de nuevo a 0, la cadena es aperiódica.

Nuestro objetivo en esta sección es calcular la probabilidad de que la cadena llegue a 0, en función del estado inicial (para que el servidor pueda atender a todos los clientes). Como veremos, existen algunos paralelismos curiosos e inesperados entre este problema y el problema de computar la probabilidad de extinción en la cadena de ramificación. Como corolario, también podremos clasificar la cadena de colas como transitoria o recurrente. Nuestro parámetro básico de interés es\( q = H(1, 0) = \P(\tau_0 \lt \infty \mid X_0 = 1) \), donde como es habitual,\( H \) es la matriz de probabilidad de golpeo y\( \tau_0 = \min\{n \in \N_+: X_n = 0\} \) es el primer tiempo positivo que la cadena está en estado 0 (posiblemente infinito). Así,\( q \) es la probabilidad de que la cola finalmente se vacíe, comenzando con un solo cliente.

El\( q \) parámetro satisface las siguientes propiedades:

1. \( q = H(x, x - 1) \)para cada\( x \in \N_+ \).
2. \( q^x = H(x, 0) \)para cada\( x \in \N_+ \).

Prueba

1. La observación crítica es que si\( x \in \N_+ \) entonces\( P(x, y) = P(1, y - x + 1) = f(y - x + 1) \) por\( y \in \{x - 1, x, x + 1, \ldots\} \). Así, la cadena, comenzando en\( x \), y hasta el tiempo que alcanza\( x - 1 \) (si lo hace), se comporta de manera estofástica como la cadena comenzando en el estado 1, y hasta llegar a 0.
2. Para llegar a 0, comenzando en estado\( x \in \N_+ \), la cadena debe primero alcanzar\( x - 1 \) y luego desde\( x - 1 \) debe llegar\( x - 2 \), hasta llegar finalmente a 0 desde el estado 1. Cada uno de estos viajes intermedios tiene probabilidad\( q \) por la parte (a) y son independientes por la propiedad Markov.

El parámetro\( q \) satisface la ecuación:\[ q = \sum_{x = 0}^\infty f(x) q^x \]

Prueba

Esto se desprende del teorema anterior al condicionar sobre el primer estado. \[ \P(\tau_0 \lt \infty \mid X_0 = 1) = \sum_{x=0}^\infty \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) \P(X_1 = x \mid X_0 = 1) \]Tenga en cuenta primero eso\( \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = 0) = 1 = q^0 \). Por otro lado, por el inmueble de Markov y el resultado anterior, Por\[ \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) = \P(\tau_0 \lt \infty \mid X_1 = x) = q^x, \quad x \in \N_+ \] supuesto\( \P(X_1 = x \mid X_0 = 1) = P(1, x) = f(x) \) para\( x \in \N \).

Tenga en cuenta que esta es exactamente la misma ecuación que consideramos para la cadena de ramificación, es decir\( \Phi(q) = q \), dónde\( \Phi \) está la función generadora de probabilidad de la distribución que gobierna el número de nuevos clientes que llegan durante cada periodo.

Figura\(\PageIndex{2}\): La gráfica de\(\phi\) en el caso recurrente

Figura\(\PageIndex{3}\): La gráfica de\(\phi\) en el caso transitorio

\( q \)es la solución más pequeña\( (0, 1] \) de la ecuación\( \Phi(t) = t \). Por otra parte

1. Si\( m \le 1 \) entonces\( q = 1 \) y la cadena es recurrente.
2. Si\( m \gt 1 \) entonces\( 0 \lt q \lt 1 \) y la cadena es transitoria..

Prueba

Esto se desprende de nuestro análisis de las cadenas de ramificación. Las gráficas anteriores muestran los dos casos. Tenga en cuenta que la condición en (a) significa que en promedio, llegan uno o menos nuevos clientes por cada cliente atendido. La condición en (b) significa que en promedio, llega más de un nuevo cliente por cada cliente atendido.

Recurrencia Positiva

Nuestro siguiente objetivo es encontrar las condiciones para que la cadena de colas sea recurrente positiva. Recordemos que\( m \) es la media de la función de densidad de probabilidad\( f \); es decir, el número esperado de nuevos clientes que llegan durante un periodo de tiempo. Como antes, vamos a\( \tau_0 \) denotar el primer tiempo positivo que la cadena está en estado 0. Suponemos que la cadena es recurrente, así\( m \le 1 \) y\( \P(\tau_0 \lt \infty) = 1 \).

Let\( \Psi \) denotar la función de generación de probabilidad de\( \tau_0 \), comenzando en el estado 1. Entonces

1. \( \Psi \)es también la función de generación de probabilidad de\( \tau_0 \) comenzar en el estado 0.
2. \( \Psi^x \)es la función de generación de probabilidad de\( \tau_0 \) comenzar en estado\( x \in \N_+ \).

Prueba

1. Las probabilidades de transición que comienzan en el estado 1 son las mismas que las que comienzan en el estado 0:\( P(0, x) = P(1, x) = f(x) \) para\( x \in \N \).
2. Comenzando en estado\( x \in \N_+ \), el tiempo aleatorio para llegar a 0 es la suma del tiempo para alcanzar\( x - 1 \), el tiempo adicional para llegar\( x - 2 \) desde\( x - 1 \), y así sucesivamente, terminando con el tiempo para llegar a 0 desde el estado 1. Estos tiempos aleatorios son independientes por la propiedad de Markov, y cada uno tiene la misma distribución que el tiempo para llegar a 0 desde el estado 1 por nuestro argumento anterior. Por último, recordemos que el PGF de una suma de variables independientes es el producto de las PGF correspondientes.

\( \Psi(t) = t \Phi[\Psi(t)] \)para\( t \in [-1, 1] \).

Prueba

Una vez más, el truco es condicionar sobre el primer estado:\[ \Psi(t) = \E\left(t^{\tau_0} \bigm| X_0 = 1\right) = \sum_{x = 0}^\infty \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = x\right) \P(X_1 = x \mid X_0 = 1) \] Primero tenga en cuenta que\( \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = 0\right) = t^1 = t \Psi^0(t) \). Por otro lado, por la propiedad de Markov y el teorema anterior,\[ \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = x\right) = \E\left(t^{1 + \tau_0} \bigm| X_0 = x\right) = t \E\left(t^{\tau_0} \bigm| X_0 = x\right) = t \Psi^x(t), \quad x \in \N_+ \] Claro\( \P(X_1 = x \mid X_0 = 1) = P(1, x) = f(x) \). De ahí que tengamos\[ \Psi(t) = \sum_{x=0}^\infty t \Psi^x(t) f(x) = t \Phi[\Psi(t)] \] El PGF de cualquier variable que tome valores enteros positivos se define en\( [-1, 1] \), y mapea este intervalo de nuevo en sí mismo. De ahí que la representación sea válida al menos para\( t \in [-1, 1] \).

El derivativo de\( \Psi \) es\[ \Psi^\prime(t) = \frac{\Phi[\Psi(t)]}{1 - t \Phi^\prime[\Psi(t)]}, \quad t \in (-1, 1) \]

Prueba

Recordemos que un PGF es infinitamente diferenciable en el intervalo abierto de convergencia. De ahí que se utilice el resultado en el teorema anterior y las reglas de producto y cadena,\[ \Psi^\prime(t) = \Phi[\Psi(t)] + t \Phi^\prime[\Psi(t)] \Psi^\prime(t) \] Resolviendo para\( \Psi^\prime(t) \) da el resultado.

Como es habitual, vamos\( \mu_0 = \E(\tau_0 \mid X_0 = 0) \), el tiempo medio de retorno al estado 0 comenzando en el estado 0. Entonces

1. \( \mu_0 = \frac{1}{1 - m} \)si\( m \lt 1 \) y por lo tanto la cadena es recurrente positiva.
2. \( \mu_0 = \infty \)si\( m = 1 \) y por lo tanto la cadena es nula recurrente.

Prueba

Recordemos que\( \Psi \) es la función de generación de probabilidad de\( \tau_0 \), a partir de 0. A partir de las propiedades básicas de las PGF sabemos que\( \Phi(t) \uparrow 1 \)\( \Psi(t) \uparrow 1 \),\( \Phi^\prime(t) \uparrow m \),, y\( \Psi^\prime(t) \uparrow \mu_0 \) como\( t \uparrow 1 \). Entonces dejando\( t \uparrow 1 \) entrar el resultado del teorema anterior, tenemos\( \mu_0 = 1 \big/ (1 - m) \) si\( m \lt 1 \) y\( \mu_0 = \infty \) si\( m = 1 \).

Entonces, para resumir, la cadena de colas es positiva recurrente si\( m \lt 1 \), nula recurrente si\( m = 1 \), y transitoria si\( m > 1 \). Dado que\( m \) es el número esperado de nuevos clientes que llegan durante un periodo de servicio, los resultados son ciertamente razonables.

Ejercicios Computacionales

Considere la cadena de cola con la función de densidad de probabilidad de llegada\( f \) dada por\( f(0) = 1 - p \)\( f(2) = p \),, donde\( p \in (0, 1) \) es un parámetro. Así, en cada periodo de tiempo, o no llegan nuevos clientes o llegan dos.

1. Encuentra la matriz de transición\( P \).
2. Encuentra la media\( m \) de la distribución de llegada.
3. Encuentra la función generadora\( \Phi \) de la distribución de llegadas.
4. Encuentra la probabilidad de\( q \) que la cola finalmente se vacíe, empezando por un cliente.
5. Clasificar la cadena como transitoria, recurrente nula o recurrente positiva.
6. En el caso recurrente positivo, encontrar\( \mu_0 \), el tiempo medio de retorno a 0.

Contestar

1. \( P(0, 0) = 1 - p \),\( P(0, 2) = p \). Para\( x \in \N_+ \),\( P(x, x - 1) = 1 - p \),\( P(x, x + 1) = p \).
2. \( m = 2 p \).
3. \(\Phi(t) = p t^2 + (1 - p)\)para\( t \in \R \).
4. \( q = 1 \)si\(0 \lt p \le \frac{1}{2} \) y\( q = \frac{1 - p}{p} \) si\( \frac{1}{2} \lt p \lt 1 \).
5. La cadena es transitoria si\( p \gt \frac{1}{2} \), nula recurrente si\( p = \frac{1}{2} \), y positiva recurrente si\( p \lt \frac{1}{2} \).
6. \( \mu_0 = \frac{1}{1 - 2 p} \)para\( p \lt \frac{1}{2} \).

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( p = \frac{1}{3} \)

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( p = \frac{2}{3} \)

Considere la cadena de colas cuya distribución de llegada es la distribución geométrica on\( \N \) con parámetro\( 1 - p \), donde\( p \in (0, 1) \). Así\( f(n) = (1 - p) p^n \) para\( n \in \N \).

1. Encuentra la matriz de transición\( P \).
2. Encuentra la media\( m \) de la distribución de llegada.
3. Encuentra la función generadora\( \Phi \) de la distribución de llegadas.
4. Encuentra la probabilidad de\( q \) que la cola finalmente se vacíe, empezando por un cliente.
5. Clasificar la cadena como transitoria, recurrente nula o recurrente positiva.
6. En el caso recurrente positivo, encontrar\( \mu_0 \), el tiempo medio de retorno a 0.

Contestar

1. \( P(0, y) = (1 - p) p^y \)para\( y \in \N \). Para\( x \in \N_+ \),\( P(x, y) = (1 - p) p^{y - x + 1} \) para\( y \in \{x - 1, x, x + 1, \ldots\} \).
2. \( m = \frac{p}{1 - p} \).
3. \(\Phi(t) = \frac{1 - p}{1 - p t}\)para\( \left|t\right| \lt \frac{1}{p} \).
4. \( q = 1 \)si\(0 \lt p \le \frac{1}{2} \) y\( q = \frac{1 - p}{p} \) si\( \frac{1}{2} \lt p \lt 1 \).
5. La cadena es transitoria si\( p \gt \frac{1}{2} \), nula recurrente si\( p = \frac{1}{2} \), y positiva recurrente si\( p \lt \frac{1}{2} \).
6. \( \mu_0 = \frac{1 - p}{1 - 2 p} \)para\( p \lt \frac{1}{2} \).

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( p = \frac{1}{3} \)

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( p = \frac{2}{3} \)

Curiosamente, el parámetro\( q \) y la clasificación de la cadena son los mismos en los dos últimos modelos.

Considere la cadena de colas cuya distribución de llegada es la distribución de Poisson con parámetro\( m \in (0, \infty) \). Así\( f(n) = e^{-m} m^n / n! \) para\( n \in \N \). Encuentra cada uno de los siguientes:

1. La matriz de transición\( P \)
2. La media\( m \) de la distribución de llegada.
3. La función generadora\( \Phi \) de la distribución de llegadas.
4. El valor aproximado de\( q \) cuándo\( m = 2 \) y cuándo\( m = 3 \).
5. Clasificar la cadena como transitoria, recurrente nula o recurrente positiva.
6. En el caso recurrente positivo, encontrar\( \mu_0 \), el tiempo medio de retorno a 0.

Contestar

1. \( P(0, y) = e^{-m} m^y / y! \)para\( y \in \N \). Para\( x \in \N_+ \),\( P(x, y) = e^{-m} m^{y - x + 1} \big/ (y - x + 1)! \) para\( y \in \{x - 1, x, x + 1, \ldots\} \).
2. El parámetro\( m \) es la media de la distribución de Poisson, por lo que la notación es consistente.
3. \(\Phi(t) = e^{m (t - 1)}\)para\( t \in \R \).
4. \( q = 1 \)si\(0 \lt m \le 1 \). Si\( m \gt 1 \) entonces\( q \) es la solución en\( (0, 1) \) de la ecuación\( e^{m (q - 1)} = q \) que se puede expresar en términos de una función especial conocida como la \( W \)función Lambert:\[ q = -\frac{1}{m} W\left(-m e^{-m}\right) \] For\( m = 2 \),\( q \approx 0.20319 \). Para\( m = 3 \),\( q \approx 0.059520 \).
5. La cadena es transitoria si\( m \gt 1 \), nula recurrente si\( m = 1 \), y positiva recurrente si\( m \lt 1 \).
6. \( \mu_0 = \frac{1}{1 - m} \)para\( m \lt 1 \).

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( m = \frac{1}{2} \)

Gráficas de\( t \mapsto \Phi(t) \) y\( t \mapsto t \) cuándo\( m = 2 \)