4.2 Cadenas de Markov¶

Una Cadena de Markov es un proceso estocástico que cumple ciertas condiciones.

Su nombre proviene del matemático ruso Andrei Markov (1856-1922).

Definiciones¶

Proceso estocástico¶

Un proceso estocástico es un conjunto de variables aleatorias

\[ \{X_0,X_1,X_2,\ldots\} \]

donde $X_t$ el estado en el tiempo $t$.

Es decir, $X_t$ puede ser:

el tiempo que hace (El tiempo en mi ciudad)
la cantidad de dinero del apostador (La ruina del apostador)
la posición de la pulga (La pulga saltarina)
el resultado de tirar la moneda (Tirar una moneda)
la clasificación del conductor por parte de la empresa de seguros (Conductores)
el tipo de letra en un texto (El Lenguaje)
el estado del coloide (Aplicación de Cadena de Markov)

en el tiempo/posición $t$. El estado del proceso estocástico en el tiempo $t$ es el valor de $X_t$.

Son modelos matemáticos dinámicos y estocásticos.

Espacio de estados¶

El espacio de estados $\mathcal{X}$ es el conjunto de valores que puede tomar $X_t$.

\[ X_t\in \mathcal{X},\quad \forall t. \]

Puede ser un conjunto infinito, pero nos limitaremos al caso en que

\[ |\mathcal{X}|=r<\infty. \]

Es decir, veremos cadenas de Markov con un conjunto finito de estados

\[ \mathcal{X}=\{x_1,x_2,\ldots,x_r\}. \]

Important

Cada uno de estos estados puede ocurrir con una cierta probabilidad y se cumple

\[ \sum_{i=1}^{r}\mathbb{P}\{X_t=x_i\}=1. \]

Trayectoria de un proceso estocástico¶

Una trayectoria es un conjunto particular de valores de las variables aleatorias $X_t$. En el ejemplo de La pulga saltarina una trayectoria puede ser

\[ 1,2,3,2,4,... \]

Si el proceso toma los valores $X_0=x_0,X_1=x_1,X_2=x_2,\ldots$ decimos que la trayectoria es

\[ x_0,x_1,x_2,\ldots \]

Note

Se suele llamar path a la trayectoria.

Propiedad Markoviana¶

Las cadenas de Markov han de cumplir la propiedad Markoviana que viene a decir que el proceso no tiene memoria.

El estado $X_{t+1}$ depende únicamente del estado $X_t$.

\[ \mathbb{P}\{X_{t+1}=x|X_t=x_t,X_{t-1}=x_{t-1},\ldots,X_0=x_0\}= \mathbb{P}\{X_{t+1}=x|X_t=x_t\}, \]

para todo $t,x,x_{t},x_{t-1},\ldots,x_0$.

Note

Un proceso estocástico que cumpla la propiedad Markoviana es una cadena de Markov.

Distribución de $X_t$¶

Dada una cadena de Markov $\{X_0,X_1,X_2,\ldots\}$ con espacio de estados $\mathcal{X}=\{x_1,x_2,\ldots,x_r\}$, cada una de las $X_t$ es una variable aleatoria, por tanto tendrá una distribución de probabilidad (discreta).

Podemos escribir esta distribución de probabilidad de un modo vectorial.

Consideramos $X_0$. Denotamos su distribución de probabilidad como

\[\begin{split} \pi^{(0)} = \begin{pmatrix} \pi_1^0 \\ \pi_2^0 \\ \vdots \\ \pi_r^0 \end{pmatrix}^T = \begin{pmatrix} \mathbb{P}\{X_0=x_1\} \\ \mathbb{P}\{X_0=x_2\} \\ \vdots\\ \mathbb{P}\{X_0=x_r\} \end{pmatrix}^T. \end{split}\]

Escribimos

\[ X_0\sim \pi^{(0)}. \]

En el ejemplo La pulga saltarina esto se corresponde con la elección aleatoria de la pulga acerca de en qué vértice empezar a saltar en tiempo 0:

\[ \mathbb{P}(\text{la pulga empieza en el vértice $i$})=\pi_i. \]

Probabilidades de transición¶

Consideramos una cadena de Markov con $r$ estados. Sea la probabilidad

\[ {\color{red}p_{ij}}= \mathbb{P}\{ X_t=x_j|X_{t-1}=x_i\}\qquad i,j=1,\ldots,r \]

de que el sistema pase del estado $i$ al estado $j$ en la iteración $t$.

Note

Consideraremos cadenas de Markov homogéneas en el tiempo. Las probabilidades de transición no dependen del tiempo:

\[ \mathbb{P}\{X_{n+1}=x_j|X_n=x_i\}= \mathbb{P}\{X_{1}=x_j|X_0=x_i\}\qquad \forall n. \]

Matriz de transición¶

Llamamos matriz de transiciones de la cadena de Markov a la matriz $r\times r$:

\[ P=(p_{ij}). \]

Son matrices cuadradas. Las filas representan el estado de entrada y las columnas el de salida.
$0\leq p_{ij}\leq 1$ (las entradas de la matriz son probabilidades).
Las $\color{red}{\text{filas}}$ suman 1:

\[ \sum_{j=1}^rp_{ij}=1,\quad i=1,\ldots,r. \]

Note

Toda matriz que verifique estas propiedades se llama matriz estocástica (por filas).

Probabilidades de transición a $n$ pasos¶

Dada una cadena de Markov con matriz de transición $P$ y condición inicial $X_0=x_i$, ya sabemos cómo calcular la distribución de probabilidad de $X_1$. En nuestra notación

\[\begin{split} X_1\sim \pi^{(1)}= \begin{pmatrix} \mathbb{P}\{X_1=x_1\}\\ \mathbb{P}\{X_1=x_2\}\\ \vdots\\ \mathbb{P}\{X_1=x_r\} \end{pmatrix}^T = \begin{pmatrix} p_{i1}\\ p_{i2}\\ \vdots\\ p_{ir} \end{pmatrix}^T. \end{split}\]

Es natural preguntarse cuál será la distribución en tiempos posteriores. Estamos interesados en conocer las probabilidades de transición a $n$ pasos, $P^{(n)}$, definidas por

\[ P_{ij}^{(n)}=\mathbb{P}\{X_{n}=x_j|X_0=x_i\}. \]

Para $n=2$ tenemos:

\[\begin{align*} \mathbb{P}\{X_2=x_j|X_0=x_i\}&= \sum_{k=1}^r \mathbb{P}\{X_2=x_j|X_1=x_k,X_0=x_i\} \mathbb{P}\{X_1=x_k|X_0=x_i\} \tag{Ley de Probabilidad Total}\\ =&\sum_{k=1}^r \mathbb{P}\{X_2=x_j|X_1=x_k\} \mathbb{P}\{X_1=x_k|X_0=x_i\} \tag{Propiedad Markoviana}\\ =&\sum_{k=1}^rP_{kj}P_{ik} \tag{Matriz de transición}\\ =&\sum_{k=1}^rP_{ik}P_{kj} \tag{Reordenando}\\ =&(P^2)_{ij} \end{align*}\]

La matriz de transición a 2 pasos $P^{(2)}=P^2$.

Tenemos el siguiente:

Theorem 1

Sea $\{X_0,X_1,\ldots\}$ una cadena de Markov con matriz de transición $P$. Las probabilidades de transición a $n$ pasos son $P^{(n)}=P^n$, es decir

\[ \mathbb{P}\{X_n=x_j|X_0=x_i\}=(P^n)_{ij}. \]

Note

Usaremos la notación $(P^n)_{ij}=P_{ij}^n$.

Warning

Lo anterior no es igual a $(P_{ij})^n$.

Dinámica¶

Supongamos que conocemos el vector de probabilidades inicial $\mathbf{\pi}^{(0)}$. ¿Cómo determinamos los siguientes vectores de probabilidad en los siguientes pasos temporales?

Estamos interesados en conocer la distribución de $X_n$, que almacenamos en $\pi^{(n)}$, es decir

\[ \pi_i^{(n)}=\mathbb{P}\{X_n=x_i\}. \]

Calculamos $\pi^{(n+1)}$ asumiendo que conocemos $\pi^{(n)}$:

\[\begin{align*} \pi_j^{(n+1)}&=\sum_{i} \mathbb{P}\{X_{n+1}=x_j|X_{n}=x_i\} \mathbb{P}\{X_n=x_i\}\tag{Probabilidad total}\\ &=\sum_{i}P_{ij}\pi_i^{(n)}\tag{definición de $\pi^{(n)}$.} \end{align*}\]

Se tiene el siguiente:

Theorem 2

Si $P$ es la matriz de transiciones de una cadena de Markov y $\pi^{(n)}$ es el vector de probabilidades en la $n$-ésima observación, entonces

\[ \pi^{(n+1)} = \pi^{(n)} P.\]

Por tanto:

\[\pi^{(n)} = \pi^{(0)} P^n , \]

siendo $\pi^{(0)}$ el vector de probabilidades inicial.

Probabilidad de una secuencia de estados¶

Nos interesamos ahora por la probabilidad de observar una secuencia de longitud $n$, $seq = \{x_1 , x_2 , \ldots , x_n \}$:

\[\mathbb{P}\{seq\}= \mathbb{P}\{ X_n=x_n,X_{n-1}=x_{n-1},\ldots,X_1=x_1\} \]

que podemos reescribir como:

\[\mathbb{P}\{seq\}= \mathbb{P}\{ X_n=x_n|X_{n-1}=x_{n-1},\ldots,X_1=x_1\} \mathbb{P}\{ X_{n-1}=x_{n-1}|X_{n-2}=x_{n-2},\ldots,X_1=x_1\}\ldots\mathbb{P}\{X_1=x_1\} \]

Gracias a la propiedad Markoviana, que dice que la probabilidad de observar $X_t$ solamente depende de la probabilidad de $X_{t-1}$, la anterior expresión se simplifica:

\[\mathbb{P}\{seq\}=\mathbb{P}\{X_n=x_n|X_{n-1}=x_{n-1}\} \mathbb{P}\{X_{n-1}=x_{n-1}|X_{n-2}=x_{n-2}\} \ldots\mathbb{P}\{X_2=x_2|X_1=x_1\}\mathbb{P}\{X_1=x_1\} \]

que simplificamos como:

\[\mathbb{P}\{seq\}= \mathbb{P}\{X_1=x_1\} \prod_{t=2}^{n}\mathbb{P}\{X_t=x_t|X_{t-1}=x_{t-1}\} \]

Important

Conocido el vector de probabilidades iniciales, $\pi^{(0)}$ , y la matriz de transiciones $P$, podemos calcular la probabilidad de observar una secuencia cualquiera (numéricamente es mejor calcular $\log \mathbb{P}\{seq\}$).

Introducción al Aprendizaje Automático

4.2 Cadenas de Markov¶

Definiciones¶

Proceso estocástico¶

Espacio de estados¶

Trayectoria de un proceso estocástico¶

Propiedad Markoviana¶

Distribución de \(X_t\)¶

Probabilidades de transición¶

Matriz de transición¶

Probabilidades de transición a \(n\) pasos¶

Dinámica¶

Probabilidad de una secuencia de estados¶