5.4: La cadena M/M/1 de Markov de tiempo de muestra

La cadena M/M/1 de Markov es un modelo de tiempo muestreado del sistema de colas M/M/1. Recordemos que la cola M/M/1 tiene llegadas de Poisson a algún ritmo y IID distribuidos exponencialmente los tiempos de servicio a algún ritmo\(\mu\). Asumimos a lo largo de esta sección que\(\lambda<\mu\) (esto se requiere para que los estados sean positivo-recurrentes). Para algunos dado pequeño incremento de tiempo\(\delta\), visualizamos observando el estado del sistema en los tiempos de muestreo\(n \delta\). Como se indica en la Figura 5.5, la probabilidad de una llegada en el intervalo de\((n-1) \delta\) a\(n \delta\) se modela como\(\lambda \delta\), independiente del estado de la cadena en el momento\((n-1) \delta\) y por lo tanto independiente de todas las llegadas y salidas previas. Así, el proceso de llegada, visto como llegadas en intervalos posteriores de duración\(\delta\), es Bernoulli, aproximándose así a las llegadas de Poisson. Esta es una aproximación de tiempo muestreado al proceso de llegada de Poisson de tasa\(\lambda\) para una cola M/M/1 de tiempo continuo.

Figura 5.5: Aproximación de tiempo muestreado a la cola M/M/1 para incremento de tiempo\(\delta\).

Cuando el sistema no está vacío (es decir, el estado de la cadena es uno o más), la probabilidad de una salida en el intervalo\((n-1) \delta\) a\(n \delta\) es\(\mu \delta\), modelando así los tiempos de servicio exponenciales. Cuando el sistema está vacío, por supuesto, las salidas no pueden ocurrir.

Tenga en cuenta que en nuestro modelo de tiempo muestreado, puede haber como máximo una llegada o salida en un intervalo\((n-1) \delta\) a\(n \delta\). Al igual que en el proceso de Poisson, la probabilidad de más de una llegada, más de una salida, o tanto una llegada como una salida en un incremento\(\delta\) es de orden\(\delta^{2}\) para el sistema M/M/1 de tiempo continuo real que se está modelando. Así, para\(\delta\) muy pequeños, esperamos que el modelo de tiempo muestreado sea relativamente bueno. En cualquier caso, ahora podemos analizar el modelo sin más aproximaciones.

Dado que esta cadena es una cadena de nacimiento y muerte, podemos usar\ ref {5.28} para determinar las probabilidades de estado estacionario; son

\(\pi_{i}=\pi_{0} \rho^{i} ; \rho=\lambda / \mu<1\)

Estableciendo la suma de la\(\pi_{i}\) a 1, nos encontramos con que\(\pi_{0}=1-\rho\), por lo

\[\pi_{i}=(1-\rho) \rho^{i} ; \quad \text { all } i \geq 0\label{5.40} \]

Así existen las probabilidades de estado estacionario y la cadena es una cadena de nacimiento y muerte, por lo que a partir del Teorema 5.3.1, es reversible. Ahora aprovechamos las consecuencias de la reversibilidad para encontrar algunos resultados bastante sorprendentes sobre la cadena M/M/1 en estado estacionario. La Figura 5.6 ilustra una ruta muestral de llegadas y salidas para la cadena. Para evitar la confusión asociada con la evolución de la cadena hacia atrás en el tiempo, nos referimos a la cadena original como la cadena que se mueve hacia la derecha y a la cadena hacia atrás como la cadena que se mueve hacia la izquierda.

Hay dos tipos de correspondencia entre la cadena que se mueve a la derecha y la que se mueve a la izquierda:

1. La cadena de movimiento a la izquierda tiene la misma descripción de cadena de Markov que la cadena que se mueve a la derecha, y por lo tanto puede verse como una cadena M/M/1 por derecho propio. Todavía etiquetamos los intervalos de tiempo muestreados de izquierda a derecha, sin embargo, para que la cadena que se mueve a la izquierda haga transiciones de\(X_{n+1}\) a\(X_{n}\) a\(X_{n-1}\). Así, por ejemplo, si\(X_{n}=i\) y\(X_{n-1}=i+1\), la cadena que se mueve a la izquierda tiene una llegada en el intervalo de\(n \delta\) a\((n-1) \delta\).
2. Cada función\(\ldots x_{n-1}, x_{n}, x_{n+1} \ldots\) de muestra de la cadena que se mueve a la derecha corresponde a la misma función\(\ldots x_{n+1}, x_{n}, x_{n-1} \ldots\) de muestra de la cadena de movimiento a la izquierda, donde\(X_{n-1}=x_{n-1}\) está a la izquierda de\(X_{n}=x_{n}\) para ambas cadenas. Con esta correspondencia, una llegada a la cadena de movimiento a la derecha en el intervalo\((n-1) \delta\) a\(n \delta\) es una salida de la cadena de movimiento a la izquierda en el intervalo\(n \delta\) a\((n-1) \delta\), y una salida de la cadena de movimiento a la derecha es una llegada a la cadena de movimiento a la izquierda. Usando esta correspondencia, cada evento en la cadena de movimiento a la izquierda corresponde a algún evento en la cadena de movimiento a la derecha.

En cada una de las propiedades de la cadena M/M/1 a derivar a continuación, se desarrolla una propiedad de la cadena de movimiento a la izquierda a través de la correspondencia 1 anterior, y luego esa propiedad se traduce en una propiedad de la cadena de movimiento a la derecha por correspondencia 2.

Propiedad 1: Dado que el proceso de llegada de la cadena de movimiento a la derecha es Bernoulli, el proceso de llegada de la cadena de movimiento a la izquierda también es Bernoulli (por correspondencia 1). Al observar una función\(x_{n+1}, x_{n}, x_{n-1}\) de muestra de la cadena que se mueve a la izquierda (es decir, usando la correspondencia 2), una llegada en el intervalo\(n \delta\) a\((n-1) \delta\) de la cadena que se mueve a la izquierda es una desviación en el intervalo\((n-1) \delta\) a\(n \delta\) de la cadena que se mueve a la derecha. Dado que las llegadas en incrementos sucesivos de la cadena de movimiento a la izquierda son independientes y tienen probabilidad\(\lambda \delta\) en cada incremento\(\delta\), concluimos que las salidas en la cadena de movimiento a la derecha son igualmente Bernoulli.

El hecho de que el proceso de salida sea Bernoulli con probabilidad de salida\(\lambda \delta\) en cada incremento es sorprendente. Tenga en cuenta que la probabilidad de una salida en el intervalo\((n \delta-\delta, n \delta]\) es\(\mu \delta\) condicional\(X_{n-1} \geq 1\) y es 0 condicional on\(X_{n-1}=0\). Ya que\(\operatorname{Pr}\left\{X_{n-1} \geq 1\right\}= 1-\operatorname{Pr}\{X_{n-1}=0\}=\rho\), vemos que la probabilidad incondicional de una salida en el intervalo\((n \delta-\delta, n \delta]\) es\(\rho \mu \delta=\lambda \delta\) como se aseveró anteriormente. El hecho de que las salidas sucesivas sean independientes es mucho más difícil de derivar sin utilizar la reversibilidad (ver ejercicio 5.13).

Propiedad 2: En la cadena original (movimiento a la derecha), las llegadas en los incrementos de tiempo posteriores\(n \delta\) son independientes de\(X_{n}\). Así, para la cadena que se mueve a la izquierda, las llegadas en incrementos de tiempo a la izquierda de\(n \delta\) son independientes del estado de la cadena en\(n \delta\). De la correspondencia entre trayectorias de muestra, sin embargo, una llegada a la cadena izquierda es una salida de cadena derecha, de manera que para la cadena que se mueve a la derecha, las salidas en los incrementos de tiempo anteriores a\(n \delta\) son independientes de\(X_{n}\), lo que equivale a decir que el estado\(X_{n}\) es independiente del anterior salidas.

Figura 5.6: Función de muestreo de la cadena M/M/1 durante un periodo ocupado y correspondientes llegadas y salidas para cadenas de movimiento derecho e izquierdo. Se considera que las llegadas y salidas ocurren entre los tiempos de muestreo, y una llegada a la cadena de movimiento a la izquierda entre el tiempo\(n \delta\) y\((n+1) \delta\) corresponde a una salida en la cadena de movimiento a la derecha entre\((n+1) \delta\) y\(n \delta\).

Esto significa que si uno observa las salidas antes de tiempo\(n \delta\), no se obtiene información sobre el estado de la cadena en\(n \delta\). Esto vuelve a ser un resultado sorprendente. Para que parezca más plausible, tenga en cuenta que un número inusualmente grande de salidas en un intervalo de\((n-m) \delta\) a\(n \delta\) indica que una gran cantidad de clientes probablemente estaban en el sistema en el momento\((n-m) \delta\), pero no parece decir mucho (y de hecho no dice exactamente nada) sobre el número permaneciendo en\(n \delta\).

El siguiente teorema resume estos resultados.

Teorema 5.4.1 (Teorema de Burke para muestreo-tiempo).

Dada una cadena M/M/1 de Markov en estado estacionario con\(\lambda<\mu\),

1. el proceso de salida es Bernoulli,
2. el estado\(X_{n}\) en cualquier momento\(n \delta\) es independiente de las salidas anteriores a\(n \delta\).

La prueba del teorema de Burke anterior no utilizó el hecho de que la probabilidad de salida es la misma para todos los estados excepto el estado 0. Por lo tanto, estos resultados siguen siendo válidos para cualquier cadena de nacimiento y muerte con llegadas a Bernoulli que sean independientes del estado actual (es decir, para las cuales\(P_{i, i+1}=\lambda \delta\) para todos\(i \geq 0\)). Un ejemplo importante de tal cadena es la aproximación del tiempo muestreado a una cola M/m/m. Aquí hay m servidores, y la probabilidad de salida del estado\(i\) en un incremento\(\delta\) es\(\mu i \delta\) para\(i \leq m\) y\(\mu m \delta\) para\(i>m\). Para que los estados sean recurrentes, y así para que exista un estado estacionario,\(\lambda\) debe ser menor que\(\mu m\). Sujeto a esta restricción, las propiedades a) y b) anteriores son válidas para las colas M/m/m de tiempo muestreado.