Siguiente:Modelos de colas estocásticosNivel anterior:Modelos de colas estocásticosPrevia:Comportamiento transitorio de M/M/1/1

El modelo M/G/1

En este caso, los tiempos de servicio son variables aleatorias independientes, no necesariamente exponenciales, aunque sí idénticamente distribuidas e independientes de los tiempos entre llegadas. $$S_i \equiv S >0 \ \text{(v.a. continua)}$$
$$f_S(s) = \text{función de densidad de } S$$
$$F_S(s) = \text{función de distribución de } S$$

Sea t_n el instante en que se produce la n-ésima salida del sistema.

Justo después de t_n, sea N_n el número de clientes en el sistema. Son variables aleatorias con valores enteros (y no negativos): $\{N_n\}_{n=1}^{+\infty}$ es un proceso estocástico en tiempo discreto.

Si existe el estado estacionario, entonces existirá

$$N=\lim_{n \rightarrow + \infty} N_n.$$

N es el número de clientes tras una salida en estado estacionario. Se pretende calcular E(N).

$$N_{n+1}= \left \{ \begin {array}{ccccc}N_n & + & \text{nº......S \text{\ unidades de tiempo} & , & N_n=0\end{array} \right.$$

Entonces

N_n+1 = N_n + A - U_n,

siendo A el número de llegadas al sistema en S unidades de tiempo (A también es v.a.) y

$$U_n= \left \{ \begin {array}{ccc}0 & si & N_n=0,\\1 & si & N_n \geq 1.\end{array} \right.$$

Sabiendo que S=s, entonces $A\equiv P(\lambda s)$. Además, usaremos la notación $E(S)=\frac{1}{\mu}$.

$$E(A)=\int_0^{+\infty} {E(A\vert S=s)} dF_S(s) = \int_0^{+\inf......bda s} dF_S(s) = \lambda E(S) = \lambda \frac {1}{\mu} =\rho.$$

El estado estacionario existe si $\rho<1$.

Como N_n+1 = N_n + A - U_n, tomando esperanzas:

$$E(N_{n+1})=E(N_n) + \rho - E(U_n).$$

Y tomando límites:

$$E(N) = E(N) + \rho - E(U)\Rightarrow$$
$$E(U)=\rho .$$

(Probabilidad de que queden clientes en el sistema tras una salida en estado estacionario)

Ahora, como paso previo para el cálculo de E(N), interesa determinar P(N_n+1=j|N_n=i). Es obvio que P(N_n+1=j|N_n=i)=0 si $j=0,1,\dots,i-2$. Basta ahora considerar $j \geq i-1$.

Caso 1: $i\geq 1 \quad (j\geq i-1)$.
 

$$P(N_{n+1}=j\vert N_n=i)=P(\text{haya \ } j-i+1 \text{\ llegadas al sistemaen\ }S\text{\ unidades}$$
$$\text{de tiempo})=\int_0^{+\infty} {P(P(\lambda s)=j-i+1)}d......{e^{-\lambda s} \frac{(\lambda s)^{j-i+1}}{(j-i+1)!}}dF_S(s).$$

Este valor no depende de n: son probabilidades estacionarias (sólo dependen del estdo del sistema). Vienen en función de la diferencia j-i. Lo llamaremos k_j-i+1 .

Una vez conocida la distribución de S, ya se puede determinar el valor anterior.

Caso 2: $i=0 \ (j\geq 0)$.

Razonando como antes, pero teniendo en cuenta que en esta ocasión deben llegar j:

$$P(N_{n+1}=j\vert N_n=0) = \dots = \int_0^{+\infty} {e^{-\lambda s}\frac {(\lambda s)^j}{j!}} dF_S(s).$$

Éste es el valor que toma k_j .
Calculemos ahora E(N). Se parte de

N_n+1=N_n + A - U_n.

Elevamos al cuadrado y tomamos esperanzas:

E(N_n+1²)=E(N_n²)+E(A²)+E(U_n²)+2E(N_nA)-2E(N_nU_n)-2E(U_nA).

Ahora se observa que por definición de U_n es E(U_n²)=E(U_n) y E(N_nU_n)=E(N_n). Además, A y N_n son independientes (el proceso de llegadas y el proceso de salidas son independientes). De igual modo, A y U_n son independientes.

E(N_n+1²)=E(N_n²)+E(A²)+E(U_n)+2E(N_n)E(A)-2E(N_n)-2E(U_n)E(A)

Tomando límites en n y usando $E(A)=\rho$:

$$E(N^2)=E(N^2)+\rho+E(A^2)+2\rho E(N) -2\rho^2 -2E(N)\Rightarrow$$
$$E(N)=\frac {\rho - 2\rho^2 + E(A^2)}{2(1-\rho)}.$$

Como $E(A^2)=Var(A) + \rho^2$, basta conocer Var(A).

Para su cálculo se necesita de estos resultados previos:

1.

Si X es una variable aleatoria, entonces Var(X)=E(X²)-E²(X).

2.

Si E(X) es finita y $h:\mathbb{R}\rightarrow \mathbb{R}$,

E_Y[E_X(h(X)|Y=y)]=E_X(X).

3.

Si E(X²) es finita, entonces

Var_Y[E_X(X|Y=y)]=Var_X(X) - E_Y[Var_X(X|Y=y)].

Los dos primeros resultados son de inmediata demostración, así como el tercero usando el segundo. Ahora, haciendo $$\sigma_S^2=Var(S)$$

y teniendo en cuenta que la variable (A|S=s) sigue una distribución $P(\lambda s)$, se tiene:

$$Var(A)=Var_S(E_A(A\vert S=s)) + E_S(Var_A(A\vert S=s))=Var_S(\lambda S) +E_S(\lambda S) =$$
$$=\lambda^2 Var_S(S) + \lambda E_S(S) =\lambda^2 \sigma_S^2 + \rho.$$

Así

$$E(N)= \frac {\rho -2\rho^2 + \rho^2 + \lambda^2 \sigma_S^2 +......o)} = \rho + \frac {\rho^2 + \lambda^2\sigma_S^2}{2(1-\rho)}.$$

Finalmente, calculemos P(N=n). Sea P_j=P(N=j).

Por el teorema de la probabiliad total,

$$P(N_{n+1}=j)=\sum_{l=0}^{j+1}P(N_{n+1}=j\vert N_n=l)P(N_n=l)= k_jP(N_n=0) +$$
$$+ k_jP(N_n=1) +k_{j-1}P(N_n=2)+\dots+k_0P(N_n=j+1).$$

Al tomar límites en n:

$$P_j=P_0 k_j + \sum_{i=1}^{+\infty} P_ik_{j-i+1} \ , \ j=0,1,2 \dots \ ,$$

siendo k_l=0 si l<0.

En notación matricial:

$$\begin{array}{rl}K=& \left(\begin{array}{ccccc}k_0 & k......s & \vdots & \vdots & \ddots\end{array}\right)\end{array}$$

La entrada (i,j) representa la probabilidad de pasar del estado i al estado j en estado estacionario.

Si P=PK para cierto $P=(P_0,P_1,P_2,\dots)$, entonces existirá el estado estacionario.

Las entradas de P vienen dadas por

$$P_j=P_0 k_j +\sum_{i=1}^{+\infty} P_i k_{j-i+1} \ , \ j=0,1,2,\ldots$$

Multiplicando por s^j+1 la j-ésima ecuación:

$$s^{j+1} P_j = s^{j+1} P_0 k_j + \sum_{i=1}^{+\infty} s^{j+1} P_ik_{j-i+1}.$$

Sumando todas las igualdades obtenidas (y representado por G la función generatriz de probabilidades de N):

$$s\sum_{j=0}^{+\infty} P_j s^j = P_0 s \sum_{j=0}^{+\infty} k_......^{+\infty} \sum_{i=1}^{j+1} s^{j+1} P_i k_{j-i+1}\Rightarrow$$
$$s G(s) = P_0 s \sum_{j=0}^{+\infty} k_j s^j +\sum_{j=0}^{+\......1} s^{j+1} P_i k_{j-i+1}= P_0 s\sum_{j=0}^{+\infty} k_j s^j +$$
$$+\sum_{l=0}^{+\infty} k_l \left( \sum_{t=1}^{+\infty} P_t s......y} k_l s^l(G(s)-P_0)=(s-1)P_0 \sum_{j=0}^{+\infty} k_j s^j +$$
$$+G(s) \sum_{l=0}^{+\infty} k_l s^l\Rightarrow$$
$$G(s)=\frac{(1-s) P_0 \sum_{j=0}^{+\infty} k_js^j}{\sum_{j=0}^{+\infty} k_j s^j -s}.$$

Como G(1)=1, utilizando la regla de l'Hôpital se tiene

$$1=G(1)= \lim_{s\rightarrow 1} \frac{(1-s)\sum_{j=0}^{+\infty}k_j s^j}{\sum_{j=0}^{+\infty} k_j s^j - s} P_0 =$$
$$=\lim_{s\rightarrow 1} \frac {-\sum_{j=0}^{+\infty}k_j s^j +......} j k_j s^{j-1}}{\sum_{j=1}^{+\infty} jk_j s^{j-1} - 1} P_0 =$$
$$= \frac{-1}{\sum_{j=1}^{+\infty} j k_j-1} P_0 = \frac{-1}{E(A)-1} P_0 = \frac {P_0}{-\rho+1}\Rightarrow$$
$$P_0 = 1-\rho.$$

Caso particular: El modelo M/D/1

Los tiempos de servicio son constantes: $\frac{1}{\mu}$.

$E(S)=\frac{1}{\mu}$

k_j = P(haya j llegadas en $\frac{1}{\mu}$ unidades de tiempo) =

$$P(P(\rho)=j)=e^{-\rho} \frac{\rho^j}{j!}.$$

Ahora

$$\sum_{j=0}^{+\infty} e^{-\rho} \frac{\rho^j}{j!} s^j =e^{-\......\frac{(\rho s)^j}{j!} = e^{-\rho}e^{\rho s} = e^{-\rho(1-s)}.$$

Luego

$$G(s)= \frac{(1-s)(1-\rho)e^{\rho(s-1)}}{e^{\rho(s-1)}-s} =\frac {(1-s)(1-\rho)}{1-se^{\rho (1-s)}}.$$

Como

$$G(s)=\sum_{n=0}^{+\infty} s P_n,$$

entonces

Gⁿ⁾(0)=n! P(N=n).

Así que

$$P_n= (1-\rho) \sum_{i=1}^n (-1)^{n-i} e^{i\rho} \left [\fra......)!} + \sum_{n-i-1>0}\frac{(i\rho)^{n-i-1}}{(n-i-1)!} \right].$$

Caso particular: el modelo M/M/1

Los tiempos de servicio son $Exp(\mu)$.
 

$$k_j=P(A=j)=\int_0^{+\infty} {P(A=j\vert S=s) f_S(s)} ds =\i......e^{-\lambda s} \frac {(\lambda s)^j}{j!} \mue^{-\mu s}} ds =$$
$$=(\lambda+\mu)^{-(j+1)} \lambda^j \mu =\left ( \frac{\rho}{1+\rho} \right )^j \frac {1}{1+\rho}$$

(Distribución geométrica) Ahora

$$\sum_{j=0}^{+\infty}k_j s^j = \sum_{j=0}^{+\infty} \left (\......rho} \right )^j \frac{1}{1+\rho} s^j = \frac{1}{1+\rho(1-s)}.$$
$$G(s)= \frac{\frac{(1-s)(1-\rho)}{1+\rho(1-s)}}{\frac{1}{1+\rho(1-s)}-s}=\frac{1-\rho}{1-\rhos}$$

Función generatriz de una distribución geométrica)

Así

$$P(N=n)=(1-\rho) \rho^n.$$