Estadística y Procesos Estocásticos Tema 4. Cadenas de Markov

class: center, middle, inverse, title-slide

# Estadística y Procesos Estocásticos <br> Tema 4. Cadenas de Markov
### <br><br><br><br><br><br><br>Grado en Ingeniería en Tecnologías de la Telecomunicación

---

background-image: url(http://www.dma.ulpgc.es/profesores/personal/stat/webEyPE/imagenes/darkGaussianBlur.jpg)
background-size: cover
class: inverse, center, middle

# 1. Recorridos Aleatorios

---
background-image: url(http://www.dma.ulpgc.es/profesores/personal/stat/webEyPE/imagenes/randomWalk.gif)
background-size: 500px
background-position: 50% 0%

## Recorrido Aleatorio

* Considérese una partícula que se mueve a lo largo de un eje horizontal ocupando las posiciones correspondientes a los números enteros:

* Inicialmente la partícula se encuentra en la posición `$X_0 = 0$`.

* En cada etapa `$n ∈ N,$` la partícula sufre un desplazamiento aleatorio `$Z_n$` , cuya distribución de probabilidad se especifica en la siguiente tabla:

* Las variables `$Z_n$` son independientes e igualmentes distribuidas

---

## Recorrido Aleatorio

Podemos representar gráficamente el recorrido aleatorio como la posición de la partícula ( `$X_n$` ) frente a la etapa ( `$n$` ):

<br>

---

## Recorrido Aleatorio

* La posición `$X_n$` de la partícula en la etapa `$n$` es:

`$$X_n=X_{n-1}+Z_n$$`

* A su vez, `$X_{n-1} = X_{n-2} + Z_{n-1}$`, por lo que:

`$$X_n=X_{n-2}+Z_{n-1}+Z_n$$`

* Repitiendo el proceso:

`$$X_n=X_{n-3}+Z_{n-2}+Z_{n-1}+Z_n$$`

`$$X_n=X_{n-4}+Z_{n-3}+Z_{n-2}+Z_{n-1}+Z_n$$`

`$$\vdots$$`

`$$X_n = X_0 + {\textstyle \sum_{k=1}^{n}Z_{k}}$$`

* Y como `$X_0=0$`:
.resalta[ 
`$$\large X_n= \sum_{k=1}^{n}Z_{k}$$`
]

---

### .blue[Algunos ejemplos de recorridos aleatorios]

---

### .blue[Algunos ejemplos de recorridos aleatorios]

---

### .blue[Algunos ejemplos de recorridos aleatorios]

---

## Esperanza de un recorrido aleatorio

Para calcular el valor esperado del recorrido aleatorio:

`$$\large X_n= \sum_{k=1}^{n}Z_{k}$$`
--

comenzamos calculando la esperanza de `$Z_k$`:
`$$Z_{k}=\begin{cases}
-1 & q\\
0 & 1-p-q\\
1 & p
\end{cases}$$`

que se obtiene fácilmente como:

`$$E\left[Z_{k}\right]=-1\cdot q + 0\cdot\left(1-p-q\right)+ 1 \cdot p = p-q$$`

De donde:

.resalta[
`$$E\left[X_n\right]=\sum_{k=1}^{n}E\left[Z_{k}\right]=n\left(p-q\right)$$`
]

---

## Varianza de un recorrido aleatorio

Calcularemos ahora la varianza del recorrido aleatorio:

`$$\large X_n={\sum_{k=1}^{n}}Z_{k}$$`

Primero calculamos la varianza de `$Z_k$`:

`$$E\left[Z_{k}^2\right]=\left(-1\right)^2\cdot q + 0^2\cdot \left(1-p-q\right) + 1^2\cdot p=p+q$$`

`$$Var\left[Z_{k}\right]=E\left[Z_{k}^2\right]-E\left[Z_{k}\right]^2=p+q-\left(p-q\right)^2$$`

Como las variables `$Z_k$` son independientes:

.resalta[

`$$Var\left(X_n\right)={\sum_{k=1}^{n}}Var\left(Z_{k}\right)=n\left(p+q-\left(p-q\right)^2\right)$$`
]

---

## Distribución límite de un recorrido aleatorio

De acuerdo con el .blue[ __teorema del límite central__], al ser `$Z_1,Z_2,\dots,Z_n$` una sucesión de variables aleatorias independientes e idénticamente distribuidas tales que `$\,\mu_{_Z}=E[Z_k]=p-q\,$` y `$\,\sigma^2_{_Z}=\textrm{Var}(Z_k)=p+q-(p-q)^2\,$` para `$\,k=1,2,\dots,n\,$`,  se tiene que:

`$$\frac{\sum_{i=1}^{n}Z_{i}-n\mu_{z}}{\sigma_{Z}\sqrt{n}}=\frac{\sum_{i=1}^{n}Z_{i}-n(p-q)}{\sqrt{p+q-(p-q)^2}\sqrt{n}}\overset{_{d}}{\longrightarrow}N\left(0,1\right)$$`
--

Por tanto, cuando `$n \rightarrow \infty$`:

.resalta[
`$$\large X_{n}=\sum_{i=1}^{n}Z_{i}\approx N\left(n\left(p-q\right),\sqrt{n\left(p+q-\left(p-q\right)^{2}\right)}\right)$$`
]

---
### .blue[Ejemplo:]
<img src="tema4-1_Cadenas_de_Markov__Recorridos_Aleatorios_files/figure-html/unnamed-chunk-6-1.png" style="display: block; margin: auto;" />

`$$E\left[X_{1000}\right]=1000\left(0.6-0.4\right)=200$$`

`$$\sqrt{Var\left(X_{1000}\right)}=\sqrt{1000\left(0.6+0.4-0.2^{2}\right)}=30.98$$`
---
### .blue[Ejemplo:]
<img src="tema4-1_Cadenas_de_Markov__Recorridos_Aleatorios_files/figure-html/unnamed-chunk-7-1.png" style="display: block; margin: auto;" />
`$$E\left[X_{1000}\right]=1000\left(0.5-0.5\right)=0$$`
`$$\sqrt{Var\left(X_{1000}\right)}=\sqrt{1000\left(0.5+0.5\right)}=31.62$$`
---
### .blue[Ejemplo:]
<img src="tema4-1_Cadenas_de_Markov__Recorridos_Aleatorios_files/figure-html/unnamed-chunk-8-1.png" style="display: block; margin: auto;" />

`$$E\left[X_{1000}\right]=1000\left(0.3-0.3\right)=0$$`
`$$\sqrt{Var\left(X_{1000}\right)}=\sqrt{1000\left(0.3+0.3\right)}=24.5$$`
---
### .blue[Ejercicio 1]

Sea `${X_n}$` un recorrido aleatorio con `$p=q=0.5$`. Calcular:

.blue[a)] `$P\left(X_{1000}<20\right)$`

.blue[b)] `$P\left(-10<X_{1000}<20\right)$`

.blue[c)] El valor `$q_{95}$` tal que `$P\left(X_{1000}\le q_{95}\right)=0.95$`

<br>

De acuerdo con el teorema del límite central:

`$$X_{1000}=\sum_{i=1}^{1000}Z_{i}\approx N\left(1000\left(0.5-0.5\right),\sqrt{1000\left(0.5+0.5-\left(0.5-0.5\right)^{2}\right)}\right)=N(0,\sqrt{1000})$$`
---
### .blue[Ejercicio 1]

Como `$X_{1000}\approx N(0,\sqrt{1000})$` entonces `$\frac{X}{\sqrt{1000}}\approx N(0,1)$`

Por tanto (llamando `$Z$` la variable normal tipificada `$N(0,1)$` ):

.blue[a)] `$P\left(X_{1000}<20\right)=P\left(\frac{X_{1000}}{\sqrt{1000}}<\frac{20}{\sqrt{1000}}\right)=P\left(Z<0.6325\right)\approx0.7365$`

<br>

.blue[b)] `$P\left(-10<X_{1000}<20\right)=P\left(X_{1000}<20\right)-P\left(X_{1000}< -10\right)=$`
`$\;\;\;\;\;=P\left(Z<\frac{20}{\sqrt{1000}}\right)-P\left(Z<\frac{-10}{\sqrt{1000}}\right)=$`
`$\;\;\;\;\;=P\left(Z<0.6325\right)-P\left(Z< -0.3162\right)\approx0.7365-0.3759=0.3606$`

<br>

.blue[c)] En la tabla de la `$N(0,1)$` se obtiene que `$P\left(Z<1.645\right)=0.95$`. Por tanto:

`$$P\left(\frac{X}{\sqrt{1000}}<1.645\right)=0.95\Rightarrow P\left(X<1.645\cdot\sqrt{1000}\right)=0.95\Rightarrow q_{95}=1.645\cdot\sqrt{1000}=52.02$$`

---
### .blue[Ejercicio 2]

Consideremos un recorrido aleatorio con parámetros `$p=0.4$` y `$q=0.3$` y supongamos que inicialmente la partícula no está en la posición `$X_0=0$`, pero se sabe que `$P(X_0=1)=0.2$`, `$P(X_0=2)=0.3$`, `$P(X_0=3)=0.1$` y `$P(X_0=4)=0.4$`. Calcular `$P(X_1=2)$`

<br>
--

Aplicando el teorema de la probabilidad total:

`$P\left(X_{1}=2\right)	=P\left(\left.X_{1}=2\right|X_{0}=1\right)P\left(X_{0}=1\right)+P\left(\left.X_{1}=2\right|X_{0}=2\right)P\left(X_{0}=2\right)+$`

`$$	+P\left(\left.X_{1}=2\right|X_{0}=3\right)P\left(X_{0}=3\right)+P\left(\left.X_{1}=2\right|X_{0}=4\right)P\left(X_{0}=4\right)=$$`
	
--

`$$=p\cdot P\left(X_{0}=1\right)+\left(1-p-q\right)\cdot P\left(X_{0}=2\right)+q\cdot P\left(X_{0}=3\right)+0\cdot P\left(X_{0}=4\right)=$$`

`$$=0.4\cdot0.2+0.3\cdot0.3+0.3\cdot0.1+0\cdot0.4=0.2$$`

---
### .blue[Ejercicio 3]

Sea `${X_n}$` un recorrido aleatorio con parámetros `$p$` y `$q$`.

Calcular la siguientes probabilidades:

<br>
.blue[a)] `$\large P\left(X_{63}=2 | X_{62}=1\right)$`

.blue[b)] `$\large P\left(X_{63}=j | X_{62}=i\right)$`

.blue[c)] `$\large P\left(X_{655}=j | X_{654}=i\right)$`

.blue[d)] `$\large P\left(X_1=1,X_2=2\right)$`

.blue[e)] `$\large P\left(X_1=1,X_2=2,X_3=1\right)$`

.blue[f)] `$\large P\left(X_1=1,X_2=2,X_3=3,X_4=3,X_5=2,X_6=1,X_7=0\right)$`

---
### .blue[Ejercicio 3]

.blue[a)] `$\large P\left(X_{63}=2 | X_{62}=1\right) =$`

--
`$\large P(Z_{63}=1)=p$`

.blue[b)] `$\large P\left(X_{63}=j | X_{62}=i\right)$`

`$$\Pr\left(X_{63}=j\mid X_{62}=i\right)=\begin{cases}
p & \,\,\,j=i+1\\
q & \,\,\,j=i-1\\
1-p-q & \,\,\,j=i \\
0 & \,\,\,\textrm{en otro caso}
\end{cases}$$`

.blue[c)] `$\large P\left(X_{655}=j | X_{654}=i\right)$`

La probabilidad es la misma que en el caso anterior ya que la distribución de los saltos no depende de _n_:

`$$\Pr\left(X_{655}=j\mid X_{654}=i\right)=\begin{cases}
p & \,\,\,j=i+1\\
q & \,\,\,j=i-1\\
1-p-q & \,\,\,j=i \\
0 & \,\,\,\textrm{en otro caso}
\end{cases}$$`

---
### .blue[Ejercicio 3]

.blue[d)] `$P\left(X_1=1,X_2=2\right)=$`

`$\hspace{3cm} = P\left(X_1=1\right)\cdot P\left(X_2=2|X_1=1\right)=P\left(Z_{1}=1\right)P\left(Z_{2}=1\right)= p\cdot p=p^2$`

<br>

.blue[e)] `$P\left(X_1=1,X_2=2,X_3=1\right) =$`

`$\hspace{3cm}=P\left(X_1=1\right)\cdot P\left(X_2=2|X_1=1\right)\cdot P\left(X_3=1|X_1=1,X_2=2\right)=$`

`$\hspace{3cm}=P\left(Z_{1}=1\right)P\left(Z_{2}=1\right)P\left(Z_{3}=-1\right)=p\cdot p\cdot q=p^2\cdot q$`

<br>

.blue[f)] `$P\left(X_1=1,X_2=2,X_3=3,X_4=3,X_5=2,X_6=1,X_7=0\right)=$`

`$\hspace{2cm}=P\left(Z_{1}=1\right)P\left(Z_{2}=1\right)P\left(Z_{3}=1\right)P\left(Z_{4}=0\right)P\left(Z_{5}=-1\right)P\left(Z_{6}=-1\right)P\left(Z_{7}=-1\right)=$`

`$\hspace{2cm}=p\cdot p\cdot p \cdot (1-p-q) \cdot q \cdot q \cdot q$`

---
## Condición de Markov

Tal como se construye el recorrido aleatorio, .red[ __si se conoce la posición de la partícula en la etapa _n_ __], las posiciones que la partícula haya ocupado en etapas anteriores .red[ __no aportan más información__] para predecir la posición que ocupará en la etapa _n+1_:

`$$\Pr\left(X_{n+1}=j\left|X_{0}=i_{0},\,X_{1}=i_{1},\,\ldots,\,X_{n-1}=i_{n-1},\,X_{n}=i\right.\right)=\Pr\left(X_{n+1}=j\left|X_{n}=i\right.\right)$$`
--

.resalta[
Así pues, __en un recorrido aleatorio, el pasado__ `$(X_0,\,X_{1},\,\ldots,\,X_{n-1})$` __no aporta información para la predicción del futuro__ `$(X_{n+1})$` __una vez que se conoce el presente__ `$(X_{n})$`. 
]

Más concretamente `$\forall n\in\mathbb{N}$`:

`$$\Pr\left(X_{n+1}=j\mid X_{n}=i\right)=\begin{cases}
p & \,\,\,j=i+1\\
q & \,\,\,j=i-1\\
1-p-q & \,\,\,j=i \\
0 & \,\,\,\textrm{en otro caso}
\end{cases}$$`

---
class: split-40

## Condición de Markov

.column[

![:scale 75%](imagenes/Markov.jpg)

[<font size="2">Andrei Markov (1856-1922)</font>](https://en.wikipedia.org/wiki/Andrey_Markov)

]

.column[
En general, una sucesión de variables aleatorias de la forma `$\left\{ X_{n};\,n\in\mathbb{N}\right\}$` definidas sobre un mismo espacio de probabilidad `$\left(\Omega,S,P\right)$` y con valores en un conjunto _E_ finito o numerable `$\left\{ X_{n}:\Omega\to E\right\}$`  verifica la .red[ __condición de Markov__] si una vez que se conoce su valor actual, los valores pasados no contienen información adicional para predecir sus valores futuros, esto es,

`$\forall n\in N;\,i_{0},\,i_{1},\,\cdots,\,i,\,j\in E$`:

`$$\Pr\left(X_{n+1}=j\left|X_{0}=i_{0},\,X_{1}=i_{1},\,\ldots,\,X_{n-1}=i_{n-1},\,X_{n}=i\right.\right)=$$`
`$$=\Pr\left(X_{n+1}=j\left|X_{n}=i\right.\right)$$`
]
<br>
.resalta[
Las sucesiones de variables aleatorias `$\left\{ X_{n};n\in\mathbb{N}\right\}$` que cumplen la condición de Markov se denominan .red[ __cadenas de Markov__].
]