Vector de estado estable en tiempo continuo

DANGER

Faltan 2 transcripciones:

• 5_19_1_vector_estable.nd

Cola de un solo servidor

La cola de un solo servidor

Encuentre el vector de probabilidad $\varphi$ de estado estable para la cola de un servidor.

Usando los valores de ${\mathrm{\Omega }}_i$, $p_i$, $q_i$ de este ejemplo:

• ${\mathrm{\Omega }}_{i-1}{p}_{i-1}=\lambda$
• ${\mathrm{\Omega }}_i{q}_i=\nu$

Para todo $i\ge 1$:

$${\varphi }_i=\frac{{\mathrm{\Omega }}_{i-1}{p}_{i-1}}{{\mathrm{\Omega }}_i{q}_i}{\varphi }_{i-1}=\frac{\lambda }{\nu }{\varphi }_{i-1}$$

Por lo tanto:

$${\varphi }_i=\frac{\lambda }{\nu }{\varphi }_{i-1}={\left(\frac{\lambda }{\nu }\right)}^2{\varphi }_{i-2}=\cdots ={\left(\frac{\lambda }{\nu }\right)}^i{\varphi }_0$$

Para $i=0,1,2,\dots$, la normalización implica que:

$$\sum _{i=0}^{\mathrm{\infty }}{\varphi }_i={\varphi }_0\sum _{i=0}^{\mathrm{\infty }}{\left(\frac{\lambda }{\nu }\right)}^i=1$$

Utilizando la fórmula de la serie geométrica:

$${\varphi }_0\sum _{i=0}^{\mathrm{\infty }}{\left(\frac{\lambda }{\nu }\right)}^i={\varphi }_0\frac{1}{1-\frac{\lambda }{\nu }}$$

para $\frac{\lambda }{\nu }<1$.

Si $\frac{\lambda }{\nu }\ge 1.$, la condición de normalización no se satisface.

Para que exista un estado estable, la tasa de partidas $\nu$ debe ser mayor que la de llegadas $\lambda$.De otra orma, al cola tiende a hacerse más grande y no alcanza una estabilidad

---

La cola de un solo servidor con $\lambda <\nu$

Para la cola de un servidor con $\lambda <\nu$, encuentre la longitud esperada de la cola en estado estable.

En el estado estable, la longitud $L$ de la cola es $i$ con probabilidad ${\varphi }_i$, para $i=0,1,2,\dots$
Nótese que la variable aleatoria $X=L+1$ está geométricamente distribuida.

Para $j\ge 1$:

$$P(X=j)=P(L=j-1)={\varphi }_{j-1}=(1-q)q^{j-1}$$

Donde:

$$q=\frac{\lambda }{\nu }$$

De esta forma, la esperanza de $X$ es:

$$E[X]=\sum _{j=0}^{\mathrm{\infty }}j(1-q)q^{j-1}=\sum _{j=0}^{\mathrm{\infty }}j{q}^{j-1}=\sum _{j=0}^{\mathrm{\infty }}j{q}^j$$

Utilizando que:

$$\sum _{j=0}^{\mathrm{\infty }}j{q}^j=\frac{q}{(1-q{)}^2}\Rightarrow E[X]=\frac{1}{1-q}=\frac{\nu }{\nu -\lambda }$$

Entonces:

$$E[L]=E[X-1]=\frac{\lambda }{\nu -\lambda }$$

La longitud esperada de la cola de un servidor para $\lambda <\nu$ es:
$\boxed{{\displaystyle {\displaystyle \frac{\lambda }{\nu -\lambda }}}}$

Se utiliza el resultado:

$$\sum _{j=0}^{\mathrm{\infty }}j{x}^{j-1}=\frac{1}{(1-x{)}^2}$$

para $-1<x<1$.

También se usa la ecuación:

$$\sum _{j=0}^{\mathrm{\infty }}j{x}^j=\frac{x}{(1-x{)}^2}$$

para $-1<x<1$.

Cola de un infinito número de servidores

La cola de un infinito número de servidores

Encuentre el vector $\varphi$ de probabilidad de estado estable para la cola con infinito número de servidores.

Si se usan los valores de ${\mathrm{\Omega }}_i$, $p_i$, $q_i$ de tal ejemplo:

$${\mathrm{\Omega }}_{i-1}{p}_{i-1}=\frac{((i-1)\nu +\lambda )\lambda }{(i-1)\nu +\lambda }=\lambda$$$${\mathrm{\Omega }}_i{q}_i=\frac{(i\nu +\lambda )i\nu }{i\nu +\lambda }=i\nu$$

Por consiguiente:

$${\varphi }_i=\frac{{\mathrm{\Omega }}_{i-1}{p}_{i-1}}{{\mathrm{\Omega }}_i{q}_i}{\varphi }_{i-1}=\frac{\lambda }{i\nu }{\varphi }_{i-1}$$

Si $i=1,2,\dots$, esta relación puede usarse recursivamente:

$$\begin{array}{rl}{\varphi }_i& =\frac{\lambda }{i\nu }{\varphi }_{i-1}\\ & =\frac{\lambda }{i\nu }\cdot \frac{\lambda }{(i-1)\nu }{\varphi }_{i-2}\\ & ⋮\\ & =\frac{1}{i!}{\left(\frac{\lambda }{\nu }\right)}^i{\varphi }_0\end{array}$$

Si se usa normalización:

$$1=\sum _{i=0}^{\mathrm{\infty }}{\varphi }_i={\varphi }_0\sum _{i=0}^{\mathrm{\infty }}\frac{(\lambda /\nu {)}^i}{i!}={\varphi }_0{e}^{\lambda /\nu }$$

Por lo tanto, ${\varphi }_0=e^{-\lambda /\nu }$. En conclusión, para la cola con infinito número de servidores, las probabilidades de estado estable son:

$${\varphi }_i=\frac{(\lambda /\nu {)}^i}{i!}{e}^{-\lambda /\nu },i=0,1,2,\dots$$

Las probabilidades en estado estable para la cola con infinito número de servidores están distribuidas de acuerdo a Poisson con parámetro $\frac{\lambda }{\nu }$. Consecuentemente, la longitud esperada de la cola con infinito de servidores es $\frac{\lambda }{\nu }$. El estado estable siempre esxiste: esto tiene sentido porque hay un infinito número de servidores.

90 % del tiempo con $N$ o menos clientes

90 % del tiempo con $N$ o menos clientes

Para la cola con infinito número de servidores con tasa de arribo $\lambda$ y tiempo medio de servicio $1/\nu$,
encuentre el número $N$ más pequeño de modo que el 90 % del tiempo habrá $N$ o menos clientes en el estado estable.

En el estado estable, la probabilidad de $i$ clientes es:

$${\varphi }_i=\frac{(\lambda /\nu {)}^i}{i!}{e}^{-\lambda /\nu }$$

Si bien $\sum _{i=0}^{\mathrm{\infty }}{\varphi }_i=1$, $N$ es el entero más pequeño que satisface:

$${\varphi }_0+{\varphi }_1+\cdots +{\varphi }_N\ge 0.90$$$$\sum _{i=0}^N{\varphi }_i=\sum _{i=0}^N\frac{(\lambda /\nu {)}^i}{i!}{e}^{-\lambda /\nu }\ge 0.90$$

Nótese que el valor de $N$ depende solamente de la razón $\lambda /\nu$.Se muestra el Cuadro 1 con valores de $\lambda /\nu$ contra $N$. El resultado es interesante: el número esperado de clientes para la cola con infinito número de servidores $\lambda /\nu$, pero solamente un poco más que este número de clientes estará presente 10% del tiempo.

$\lambda /\nu$	$N$	$\lambda /\nu$	$N$
0.5	1	20	26
2	2	50	59
5	8	100	113
10	14

Cuadro: Número $N$ más pequeño para que el 90 % del tiempo haya $N$ o menos clientes en el estado estable.

El sistema de colas M/M/s

Un sistema M/M/s tiene un proceso de llegada y de servicio tipo Markov (de ahí la M) y un número $s$ de servidores.

En un sistema M/M/s, las llegadas son descritas por un proceso de Poisson con parámetro $\lambda$. Cada uno de los $s$ servidores tiene un tiempo de servicio exponencial con parámetro $\nu$.
El proceso $X(t)=i$ (notación abreviada $X_t$) describe el estado del sistema al tiempo $t$ para $S=\{0,1,\dots \}$ (es decir, $i\ge 0$).

Únicamente con $\rho =\lambda /(s\nu )<1$ el sistema alcanza un estado estacionario, donde:

$${\mathrm{\Omega }}_0=\lambda {\mathrm{\Omega }}_{i\to i-1}=\{\begin{array}{ll}i\nu & \text{para }0<i<s\\ s\nu & \text{para }i\ge s\end{array}$$$${\varphi }_0={[\sum _{k=0}^{s-1}\frac{(s\rho {)}^k}{k!}+\frac{(s\rho {)}^s}{s!(1-\rho )}]}^{-1}$$$${\varphi }_i=\{\begin{array}{ll}{\displaystyle \frac{(s\rho {)}^i}{i!}{\varphi }_0}& \text{para }i<s\\ {\displaystyle \frac{s^s{\rho }^i}{s!}{\varphi }_0}& \text{para }i\ge s\end{array}$$

Notación alternativa M/M/c

En algunas referencias es posible encontrar esta notación equivalente:

$${\pi }_0={[\left(\sum _{k=0}^{c-1}\frac{(c\rho {)}^k}{k!}\right)+\frac{(c\rho {)}^c}{c!(1-\rho )}]}^{-1}$$$${\pi }_k=\{\begin{array}{ll}{\pi }_0{\displaystyle \frac{(c\rho {)}^k}{k!}}& \text{para }0<k<c\\ {\pi }_0{\displaystyle \frac{(c\rho {)}^k{c}^{c-k}}{c!}}& \text{para }k\ge c\end{array}$$

donde $c$ es el número de servidores, $k$ es el estado (o número de clientes en el sistema), ${\pi }_k$ es la probabilidad en estado estable y $\rho =\lambda /(c\nu )$.

Asimismo, es posible describir el número promedio de clientes en el sistema como:

$$L=\frac{\lambda }{\nu }+\frac{\rho (s\rho {)}^s}{s!(1-\rho {)}^2}{\varphi }_0$$

Y el número promedio de clientes en una fila (cuando todos los servidores están ocupados), dado como:

$$L_q=\frac{\rho (s\rho {)}^s}{s!(1-\rho {)}^2}{\varphi }_0=L-\frac{\lambda }{\nu }$$

Parámetros del sistema

Para una corriente de arribo de Poisson con parámetro $\lambda$ y un tiempo de servicio exponencial con parámetro $\nu$, con un solo servidor $s=1$, las probabilidades de estado estable son:

$${\mathrm{\Omega }}_0=\lambda {\mathrm{\Omega }}_{i\to i-1}=\nu$$$${\varphi }_0=1-\frac{\lambda }{\nu }=1-\rho$$$${\varphi }_i=(1-\frac{\lambda }{\nu }){\left(\frac{\lambda }{\nu }\right)}^i=(1-\rho ){\rho }^i$$

El número promedio de clientes en el sistema es:

$$L=\frac{\rho }{1-\rho }=\frac{\lambda }{\nu -\lambda }$$

Y el número promedio de clientes en una fila (cuando el servidor está ocupado) es:

$$L_q=\frac{{\lambda }^2}{\nu (\nu -\lambda )}=\frac{{\rho }^2}{1-\rho }$$

Servidor web

Un servidor web es modelado como un sistema M/M/1 con una tasa de arribo de 2 solicitudes por minuto.
Se desea tener 3 solicitudes o menos en fila (más una que está siendo atendida) el 99% del tiempo.
¿Qué tan rápido debe ser el servicio? $\nu$ es solicitudes atendidas por minuto.

El estado $i$ es el número de clientes en el sistema. La longitud de la fila es $L_q=i-1$ (en virtud de la solicitud que está siendo atendida en $s=1$ servidores). Es posible encontrar:

$$P(\text{5 o más clientes en el sistema})=\sum _{i=5}^{\mathrm{\infty }}(1-\rho ){\rho }^i=1-\sum _{i=0}^4(1-\rho ){\rho }^i={\rho }^5$$

que depende de $\rho =\frac{\lambda }{\nu }$ y del parámetro de servicio $\nu$ buscado.

De los datos del problema: $\lambda =2$. Para tener una fila de 3 o menos clientes el 99% del tiempo se necesita:

$$P(5\text{ o más clientes en el sistema})={\rho }^5={\left(\frac{\lambda }{\nu }\right)}^5\le 0.01$$

Cantidad de solicitudes por minuto para garantizar hasta 3 personas en la fila

$${\nu }^5\ge \frac{{\lambda }^5}{0.01}=\frac{2^5}{0.01}=3200\Rightarrow \nu \ge 5.024$$

Teorema del límite

Suponga las siguientes condiciones para el proceso de nacimiento y muerte:

1. $p_0=1$
2. $0<p_i<1$ para $i=1,2,\dots$
3. $q_N=1$ si $S=\{0,1,2,\dots ,N\}$
4. ${\mathrm{\Omega }}_i>0$ para $i\in S$

Suponga que $\varphi$ es un vector de probabilidad que satisface:

$${\varphi }_i=\left(\frac{{\mathrm{\Omega }}_{i-1}{p}_{i-1}}{{\mathrm{\Omega }}_i{q}_i}\right){\varphi }_{i-1}$$

para i = 1,2,...

Entonces:

1. Dado cualquier vector de probabilidad inicial $\rho$,

$$P(X_t=i\mid \text{vector inicial }\rho )\to {\varphi }_i$$

cuando $t\to \mathrm{\infty }$ para cada $i\in S$.

2. Si el vector de probabilidad inicial es $\rho$ = $\varphi$, entonces

$$P(X_t=i\mid \text{vector inicial }\varphi )={\varphi }_i$$

para todo $t\ge 0$ para $i\in S$.

Primer resultado Sin importar el estado inicial en el tiempo $t=0$, el proceso se hallará en el estado $i$ con probabilidad ${\varphi }_i$ conforme $t$ se hace grande.

Segundo resultado Si $\varphi$ se usa como el vector inicial de probabilidad, entonces $\varphi$ será el vector de probabilidad para todo tiempo $t\ge 0$.

Las condiciones del teorema sobre ${\mathrm{\Omega }}_i,p_i,q_i$ son esenciales: ningún estado es absorbente y cualquier estado puede alcanzarse desde cualquier otro estado.

Videos y referencias en internet

• ¿Qué es una cadena de Markov?

  Luis Rincón https://youtu.be/Trf9P7DnOHQ

• Origin of Markov chains | Journey into information theory | Computer Science

  Khan Academy Labs https://youtu.be/Ws63I3F7Moc