Estadística y Procesos Estocásticos Tema 5: Procesos de Nacimiento y Muerte

class: center, middle, inverse, title-slide

# Estadística y Procesos Estocásticos Tema 5: Procesos de Nacimiento y Muerte
### Grado en Ingeniería en Tecnologías de la Telecomunicación

---

## 1. Introducción.

* Este tipo de procesos, como sugiere su propio nombre, se comenzó a utilizar inicialmente en demografía para modelar el tamaño de una población.

* Constituyen la herramienta básica para modelar el teletráfico:

+ un nacimiento representa el acceso de un _cliente_ a un sistema (por ejemplo, un paquete de datos que accede a un router)

+ una muerte representa la salida de un cliente del sistema.

* Cuando las llegadas y salidas a un sistema se producen siguiendo patrones aleatorios, se forman _lineas de espera_ o _colas_. El _protocolo de servicio_ especifica en qué orden son atendidos los sucesivos clientes.

* Por tanto estos procesos constituyen la base para el modelado y gestión de tráfico, así como para el dimensionamiento de recursos en redes.

---

### .blue[Ejemplo: Sistema de colas]

<center>
 
![](imagenes/cola.png)

</center>

---

## 2. Procesos de nacimiento y muerte

* Sea `$N(t)$` el número de clientes en el sistema en el instante `$t$`.

* Sea `$h$` un valor pequeño ( `$h\rightarrow 0$` ). Llamaremos:

+ `$L_{(t,t+h]}$` = número de llegadas que ocurren en el intervalo `$(t,t+h]$`

+ `$S_{(t,t+h]}$` = número de salidas en el mismo intervalo

* Sea `$o\left(h\right)$` un valor infinitesimal respecto a `$h$`, esto es, `$\underset{h\rightarrow0}{\lim}\frac{o\left(h\right)}{h}=0$`

---

* Supondremos que en un lapso de tiempo infinitesimal .red[ocurre como máximo una única llegada]:

+ `$\Pr\left(L_{(t,t+h]}=1\left|N\left(t\right)=n\right.\right)=\lambda_{n}h+o\left(h\right)$`
 
 + `$\Pr\left(L_{(t,t+h]}=0\left|N\left(t\right)=n\right.\right)=1-\lambda_{n}h+o\left(h\right) \hspace{2cm} \lambda_n=$` __Tasa de llegada__ 
 
 + `$\Pr\left(L_{(t,t+h]}>1\left|N\left(t\right)=n\right.\right)=o\left(h\right)$`

* Supondremos también que en un lapso de tiempo corto ocurre .red[como máximo una única salida]:
 
 + `$\Pr\left(S_{(t,t+h]}=1\left|N\left(t\right)=n\right.\right)=\mu_{n}h+o\left(h\right)$`
 
 + `$\Pr\left(S_{(t,t+h]}=0\left|N\left(t\right)=n\right.\right)=1-\mu_{n}h+o\left(h\right) \hspace{2cm} \mu_n=$` __tasa de servicio__
 
 + `$\Pr\left(S_{(t,t+h]}>1\left|N\left(t\right)=n\right.\right)=o\left(h\right)$`
 
--

* Las llegadas y las salidas se producen de forma __independiente__.
    
--

* `$\lambda$` y `$\mu$` dependen solo de `$n$` y no de `$t$`.

---

### .blue[Ecuaciones del proceso de Nacimiento-Muerte]
 
Llamando: `$\hspace{4cm}\large{P_{n}\left(t\right)=\Pr\left({N\left(t\right)=n}\right)}$`

Se tiene que:

`$$\large{P_{n}\left(t+h\right)=P_{n}\left(t\right)\left(1-\lambda_{n}h\right)\left(1-\mu_{n}h\right)+P_{n-1}\left(t\right)\lambda_{n-1}h\left(1-\mu_{n-1}h\right)+}$$`

`$$\large{+P_{n+1}\left(t\right)\left(1-\lambda_{n+1}h\right)\mu_{n+1}h+o\left(h\right)}$$`  
--

y para `$n=0$`:

`$$\large{P_{0}\left(t+h\right)=P_{0}\left(t\right)\left(1-\lambda_{0}h\right)+P_{1}\left(t\right)\left(1-\lambda_{1}h\right)\mu_{1}h+o\left(h\right)}$$`
--

De donde:

.resalta[

`$$\Large{P'_{n}\left(t\right)=-\left(\lambda_{n}+\mu_{n}\right)P_{n}\left(t\right)+\lambda_{n-1}P_{n-1}\left(t\right)+\mu_{n+1}P_{n+1}\left(t\right)}$$`

`$$\Large{P'_{0}\left(t\right)=-\lambda_{0}P_{0}\left(t\right)+\mu_{1}P_{1}\left(t\right)}$$`
]

---
### .blue[Ecuaciones del proceso de Nacimiento-Muerte]

Si el sistema anterior alcanza el equilibrio (es ergódico), entonces:

`$\hspace{3cm}\large{\lim\limits _{t\to\infty}P_{n}\left(t\right)=p_{n}}\hspace{1cm}$` y por tanto `$\hspace{1cm}\large{\lim\limits _{t\to\infty}P'_{n}\left(t\right)=0}$`

y las ecuaciones anteriores se transforman en:

.resalta[

`$$\Large{0=-\left(\lambda_{n}+\mu_{n}\right)p_{n}+\lambda_{n-1}p_{n-1}+\mu_{n+1}p_{n+1}\;\;;\;\;\;n\geqslant1}$$`
`$$\Large{0=-\lambda_{0}p_{0}+\mu_{1}p_{1}}$$`

]

---
### .blue[Ecuaciones del proceso de Nacimiento-Muerte]

Estas ecuaciones se pueden resolver recursivamente: de la segunda ecuación se obtiene:

`$$0=-\lambda_{0}p_{0}+\mu_{1}p_{1}\Rightarrow p_{1}=\frac{\lambda_{0}}{\mu_{1}}p_{0}$$`
--

Asimismo, de la primera ecuación se sigue que:

`$$p_{n+1}=\frac{1}{\mu_{n+1}}\left(\left(\lambda_{n}+\mu_{n}\right)p_{n}-\lambda_{n-1}p_{n-1}\right)$$`
--

Por tanto:

`$$p_{2}=\frac{1}{\mu_{2}}\left(\left(\lambda_{1}+\mu_{1}\right)p_{1}-\lambda_{0}p_{0}\right)=\frac{1}{\mu_{2}}\left(\left(\lambda_{1}+\mu_{1}\right)\frac{\lambda_{0}}{\mu_{1}}p_{0}-\lambda_{0}p_{0}\right)=\frac{\lambda_{1}\lambda_{0}}{\mu_{2}\mu_{1}}p_{0}$$`
--

Podemos proceder reiteradamente del mismo modo para obtener `$p_3$`, `$p_4$`, `$\dots$`

---

### .blue[Ecuaciones del proceso de Nacimiento-Muerte]

La solución general es de la forma:

.resalta[
`$$\Large{p_{n}=\frac{{\lambda_{0}\lambda_{1}\;...\;\lambda_{n-1}}}{{\mu_{1}\mu_{2}\;...\;\mu_{n}}}\cdot p_{0}}$$`
]

Dado que la sucesión `$\left\{ p_{n};\,\,n=0,1,...\right\}$`  es una distribución de probabilidad, verificará que `$\sum\limits _{n=0}^{\infty}p_{n}=1$`, de donde se deduce que:

.resalta[

`$$\Large{p_{0}=\frac{1}{{1+\sum\limits _{n=1}^{\infty}{\prod\limits _{i=0}^{n-1}{\frac{{\lambda_{i}}}{{\mu_{i+1}}}}}}}}$$`
]

---

## Sistemas de Colas

* Los procesos de nacimiento-muerte permiten modelar aquellos sistemas de colas en los que las tasas de llegada ( `$\lambda_n$` ) y servicio ( `$\mu_n$` ) de los clientes dependen únicamente de la ocupación del sistema en cada momento.

* Las ecuaciones anteriores nos proporcionan las probabilidades de que haya n clientes en el sistema ( `$n\geq0$` ) cuando éste se encuentra en equilibrio.

* .red[Sistema de colas en equilibrio:]  se considera como tal un sistema de colas una vez que ha transcurrido el tiempo suficiente para que la distribución de probabilidad de la ocupación del sistema alcance el estado estacionario. La cola fluctúa constantemente de forma dinámica, llenándose y vaciándose, y el valor de `$p_{n}$` representa la probabilidad de encontrar `$n$` clientes en el sistema en cualquier futuro instante arbitrario.

---

## Elementos de un sistema de colas.

* `$C_{n}$`: representa el n-ésimo cliente que llega al sistema.

* `$\tau_{n}$`: instante de llegada de `$C_{n}$`.

* `$T_{n}$`: tiempo entre las llegadas de `$C_{n-1}$` y `$C_{n}$`, ( `$T_{n}=\tau_{n}-\tau_{n-1}$` ).

* `$X_{n}$`: .red[ __Duración del servicio__] para el cliente `$C_{n}$`.

* `$W_{n}$`: .red[ __Tiempo de espera en cola__] del cliente `$C_{n}$`.

* `$S_{n}$`: .red[ __Tiempo en el sistema__] ( `$W_{n}+X_{n}$` ) del cliente `$C_{n}$`.

* `$N\left(t\right)$`: .red[ __Número de clientes en el sistema__] en el instante `$t$`.

* `$Q\left(t\right)$`: .red[ __Tamaño de la cola__] en el instante `$t$`.

---

## Intensidad de tráfico

`$$\Large{\rho_{k}=\frac{\lambda_{k}}{\mu_{k}}}$$`
--

* Mide la relación entre el número de llegadas y el número de salidas por unidad de tiempo.

* .red[ __Condición de equilibrio__]: La condición necesaria y suficiente para que un proceso de nacimiento-muerte sea ergódico (alcance el equilibrio) es que exista un valor `$k_{0}$` tal que para todo `$k\geq k_{0}$`:

.resalta[
`$$\Large\rho_{k}=\frac{\lambda_{k}}{\mu_{k}}<1$$`
]

* Esta condición indica que el sistema sólo alcanza el equilibrio si a partir de cierto número de clientes en el sistema ( `$k_{0}$` ), la velocidad a que llegan los clientes es inferior a la velocidad con que son atendidos.

---
## Fórmula de Little

Esta fórmula indica que en un sistema de colas en equilibrio:

.resalta[

`$$\Large E\left[N\right]=\frac{E\left[S\right]}{E\left[T\right]}$$`
]

donde:

* `$E\left[T\right]$`: tiempo esperado entre llegadas.

* `$E\left[S\right]$`: tiempo esperado que permanece en el sistema un cliente arbitrario.

* `$E\left[N\right]$`: número esperado de clientes en el sistema en un instante arbitrario. 
--

Si `$\lambda$` es el número esperado de llegadas por unidad de tiempo,  se tiene que `$\lambda=1/E\left[T\right]$` y la fórmula de Little puede expresarse también como:

.resalta[

`$$\Large E\left[N\right]=\lambda E\left[S\right]$$`
]

---

### .blue[Justificación de la fórmula de Little]

En un sistema de colas en equilibrio, .red[el número esperado de clientes a la llegada de un cliente arbitrario debe coincidir con el número esperado a su salida]. Tenemos:

* Cuando un cliente arbitrario accede al sistema en equilibrio, el número esperado de clientes que encuentra es `$E\left[N\right]$`.

* Cuando se marcha del sistema, habrá permanecido en él durante un tiempo esperado `$E\left[S\right]$`.

* Como el tiempo medio entre llegadas es `$E\left[T\right]$`, durante el tiempo `$E\left[S\right]$` habrá llegado un número esperado de clientes `$E\left[S\right]/E\left[T\right]$`.

* Si la disciplina de la cola es FIFO (First In First Out, los clientes son atendidos en su orden estricto de llegada), cuando el cliente se vaya, los `$E\left[S\right]/E\left[T\right]$` que han llegado durante su permanencia en el sistema son los que quedan en el sistema.

---

## Notación de Kendall

Establece una clasificación de los distintos modelos de colas en los que cada cliente debe recibir un solo servicio. Consiste en un un código de la forma .red[ __L/S/m/K/N__], donde:

* .red[ __L__]: distribución de probabilidad de los tiempos entre llegadas de clientes a la cola.

* .red[ __S__]: distribución de los tiempos de servicio.

* .red[ __m__]: número de servidores.

* .red[ __K__]: capacidad (buffer) disponible en el sistema para acumular los clientes en cola (si no se especifica, se entiende que la capacidad del sistema es infinita)

* .red[ __N__]: tamaño de la población de la que proceden los clientes. No se especifica si el tamaño es infinito.

---
## Notación de Kendall

Los códigos más habituales para las distribuciones de los tiempos entre llegadas y de servicio son: M (exponencial), G (general), y D (determinista). Ejemplos de sistemas descritos por la notación de Kendall son:

--

* .red[ __M/M/1__]: Llegadas con distribución de Poisson con tasa constante `$\lambda$` (y por tanto tiempos entre llegadas con distribución exponencial), tiempos de servicio exponenciales y un solo servidor.

--

* .red[ __M/M/1/K__]: idéntico al anterior, pero con un buffer de capacidad finita K.

--

* .red[ __M/G/1__]: Llegadas con distribución de Poisson con tasa constante `$\lambda$`, tiempos de servicio con distribución general, un único servidor.

---
## Colas M/M/1

Consiste en un único canal de servicio o servidor en el que las llegadas y salidas se producen de acuerdo con un proceso de nacimiento y muerte con tasas de llegada y salida respectivas:

`$$\begin{array}{c}
\lambda_{n}=\lambda\,\,\,\,\,\,n=0,1,2,\cdots\\
\mu_{n}=\mu\,\,\,\,\,\,n=1,2,3,\cdots
\end{array}$$`

En este sistema:

* Los tiempos entre dos llegadas consecutivas, `$\left\{ T_{n};n\in N\right\}$`, son variables aleatorias independientes y con distribución de probabilidad exponencial de parámetro `$\lambda$`.

* Los sucesivos tiempos de servicio `$\left\{ X_{n};n\in N\right\}$`  son también variables aleatorias independientes y con distribución de probabilidad exponencial de parámetro `$\mu$`.

* La distribución de equilibrio es:

`$$p_{n}=\frac{{\lambda_{0}\lambda_{1}\;...\;\lambda_{n-1}}}{{\mu_{1}\mu_{2}\;...\;\mu_{n}}}\cdot p_{0} = 
\left(1-\frac{\lambda}{\mu}\right)\cdot\left(\frac{\lambda}{\mu}\right)^{n}\;\;;\;\;n=0,1,2,...$$`

---

## Colas M/M/1:

Por tanto, en el equilibrio, llamando `$\large \rho=\frac{\lambda}{\mu}$` la probabilidad de que haya N clientes en el sistema sigue una .blue[distribución geométrica]:

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

Para calcular la esperanza y la varianza de N hallamos la función característica:

`$$\varphi\left(t\right)=E\left[e^{itN}\right]=\sum_{n=0}^{\infty}e^{itn}P\left(N=n\right)=\sum_{n=0}^{\infty}e^{itn}\left(1-\rho\right)\rho^{n}=\left(1-\rho\right)\sum_{n=0}^{\infty}\left(\rho e^{it}\right)^{n}=\frac{1-\rho}{1-\rho e^{it}}$$`
--

Su derivada es:

`$$\varphi'\left(t\right)=\frac{\left(1-\rho\right)i\rho e^{it}}{\left(1-\rho e^{it}\right)^{2}}$$`
--

y por tanto:

`$$\large E\left[N\right]=\frac{1}{i}\varphi'\left(0\right)=\frac{\rho}{1-\rho}=\frac{\lambda/\mu}{1-\lambda/\mu}=\frac{\lambda}{\mu-\lambda}$$`
---

## Colas M/M/1:

* Para que exista solución de equilibrio debe ocurrir que `$\lambda<\mu$`.

* `$\large E\left[N\right]=\frac{\rho}{1-\rho}=\frac{\lambda}{{\mu-\lambda}}$`

* `$\large Var\left(N\right)=E\left[N^{2}\right]-\left(E[N]\right)^{2}=\frac{1}{i^{2}}\varphi''\left(0\right)-\left(\frac{\rho}{1-\rho}\right)^{2}=\dots=\frac{\rho}{\left(1-\rho\right)^{2}}$`

* Aplicando la fórmula de Little:

`$$E\left[N\right]=\lambda E\left[S\right]\Rightarrow\frac{\rho}{1-\rho}=\lambda E\left[S\right]\Rightarrow E\left[S\right]=\frac{\rho}{\lambda\left(1-\rho\right)}=\frac{1/\mu}{1-\rho}$$`  
--

* El tiempo medio en cola es `$E\left[W\right]=E\left[S\right]-E\left[X\right]=E\left[S\right]-\frac{1}{\mu}$`:

`$$E\left[W\right]=\frac{\rho/\mu}{1-\rho}$$`

* De las expresiones anteriores se sigue que cuando `$\rho\rightarrow0$`: `$E\left[S\right]\rightarrow\infty$` y `$E\left[W\right]\rightarrow\infty$`

---

## Cola con capacidad finita M/M/1/C:

* En las condiciones del sistema M/M/1, si la capacidad del buffer es finita `$C$` podemos modelar su comportamiento mediante un proceso de nacimiento-muerte con:

`$$\lambda_{k}	=	\left\{ \begin{array}{ll}
\lambda & \,\,\,k<C\\
0 & \,\,\,k\geq C
\end{array}\right.
\hspace{1cm}\mu_{k}	=	\mu,\,\,\,k=1,2,3,...,C$$`

* Este sistema siempre alcanza el equilibrio, pues para `$k\geq C$` se tiene `$\lambda_{k}/\mu_{k}=0$`.

* Las probabilidades de equilibrio son:

.resalta[
`$$\Large p_{k}=\left\{ \begin{array}{ll}
\frac{{1-\left({\lambda/\mu}\right)}}{{1-\left({\lambda/\mu}\right)^{C+1}}}\left({\frac{\lambda}{\mu}}\right)^{k} & \,\,\,\,\,0\leq k\leq C\\
\,\,\,\,\,\,\,\,\,\,\,\,\,0 & \,\,\,\,\,\,k>C
\end{array}\right.$$`
]

---

## Sistemas con capacidad finita M/M/1/C:

* En este sistema la probabilidad de que un cliente sea rechazado (se pierda) coincide con la probabilidad de encontrar el sistema lleno a su llegada:

.resalta[
`$$\large P\left(\textrm{Pérdida}\right)=p_{C}=\frac{{1-\left({\lambda/\mu}\right)}}{{1-\left({\lambda/\mu}\right)^{C+1}}}\left({\frac{\lambda}{\mu}}\right)^{C}$$`
]

--

* En la práctica resulta de interés calcular el valor de `$C$` que garantice que la probabilidad de pérdida está por debajo de un umbral preespecificado `$p_u$`

---

## Sistemas con más de un servidor: M/M/m
 
* Generalizan el modelo M/M/1 al caso de m servidores. El cliente que ocupa la primera posición de la cola es atendido por el primer servidor que queda libre.

* Podemos modelar este sistema mediante las tasas de llegada y servicio siguientes:

`$$\lambda_k = \lambda \;\;\forall k$$`

`$$\mu_{k}=\left\{ \begin{array}{ll}
k\mu & \,\,\,0\le k\le m\\
m\mu & \,\,\,k\geq m
\end{array}\right.$$`

--

* La intensidad de tráfico en este sistema es:

`$$\rho=\lambda/m\mu$$`

---
## Sistemas con más de un servidor: M/M/m

* Distribución de equilibrio:

.resalta[

`$$\large p_{k}=\left\{ \begin{array}{ccc}
\begin{matrix}p_{0}\frac{{\left(\rho m\right)^{k}}}{{k!}}\end{matrix} &  & k\leq m\\
\begin{matrix}p_{0}\frac{\rho^{k}m^{m}}{{m!}}\end{matrix} &  & k\geq m
\end{array}\right.{\,\,\,\,\text{ }}p_{0=}=\left[{\sum\limits _{k=0}^{m-1}{\frac{{\left({m\rho}\right)^{k}}}{{k!}}+\frac{{\left({m\rho}\right)^{m}}}{{m!\left({1-\rho}\right)}}}}\right]^{-1}$$`
]

* Probabilidad de que un cliente tenga que hacer cola (fórmula C de Erlang):

`$$\large Q_{m}=\sum\limits _{k=m}^{\infty}{p_{k}}=\frac{{\frac{{\left({m\rho}\right)^{m}}}{{m!}}\left({\frac{1}{{1-\rho}}}\right)}}{{\left[{\sum\limits _{k=0}^{m-1}{\frac{{\left({m\rho}\right)^{k}}}{{k!}}+\frac{{\left({m\rho}\right)^{m}}}{{m!\left({1-\rho}\right)}}}}\right]}}$$`

---

## Sistemas con más de un servidor: M/M/m

* Número medio de clientes en el sistema:

`$$\large E\left[N\right]=\frac{\rho}{1-\rho}Q_{m}+m\rho$$`

* Tiempo medio en el sistema:

`$$\large E\left[S\right]=\frac{E\left[N\right]}{\lambda}=\frac{1}{m\mu-\lambda}Q_{m}+\frac{1}{\mu}$$`

* Tiempo medio en cola:

`$$\large E\left[W\right]=\frac{1}{m\mu-\lambda}Q_{m}$$`