1. Cadenas de Markov

Una cadena de Marvok es un proceso evolutivo que consiste de un número finito de estados en cual la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior con unas probabilidades que están fijas. Para motivar este concepto exploremos el siguiente ejemplo:

Ejemplo: Supongamos que hay tres centros principales de camiones de una empresa. Cada mes, la mitad de los que están en Boston y en Los Angeles, van a Chicago, la otra mitad permanece donde está y los camiones de Chicago se dividen igualmente entre Boston y L.A. Lo anterior se puede resumir con la siguiente figura:

Si inicialmente la compañía tenía $100, 200$ y $300$ camiones en Boston, Chicago y L.A. respectivamente, encontrar la distribuciones de camiones después de un mes y después de dos meses en las tres ciudades.

Solución: Denotemos por $a_{k}$, $b_{k}$ y $c_{k}$ la cantidad de camiones en Boston, Chicago y L.A. respectivamente, después de $k$-meses. Utilizando la información dada se tiene que después de un mes, la distribución de los camiones será: \begin{align*} a_1=&\frac{1}{2}a_0+\frac{1}{2}b_0=50+100=150,\\ b_1=&\frac{1}{2}a_0+\frac{1}{2}c_0=50+150=200,\\ c_1=& \frac{1}{2}b_0+\frac{1}{2}c_0 =100+150=250.\end{align*} Y después de $2$ meses, vemos que la distribución será: \begin{align*} a_2=&\frac{1}{2}a_{1}+\frac{1}{2}b_{1}=75+100=175, \\ b_2=&\frac{1}{2}a_{1}+\frac{1}{2}c_{1}=75+125=200,\\ c_1=&\frac{1}{2}b_{1}+\frac{1}{2}c_{1} =100+125=225. \end{align*} Los cálculos de este ejemplo se pueden realizar de manera más conveniente si utilizamos notación matricial. Para ver esto, denotemos por $x_{k}$ al vector de probabilidades en el $k$-ésimo mes, es decir, denotemos $x_{k}=\left[ \begin{array}{c}a_{k}\\ b_{k} \\ c_{k} \end{array} \right]$. El cálculo realizado para el primer mes se puede realizar de la siguiente manera: \[ x_{1}=\left[ \begin{array}{c}a_{1}\\ b_{1} \\ c_{1} \end{array} \right] =\left[ \begin{array}{c}1/2 & 1/2 & 0\\ 1/2 & 0 & 1/2 \\0& 1/2 &1/2 \end{array} \right] \left[ \begin{array}{c}a_{0}\\ b_{0} \\ c_{0} \end{array} \right] \] En otras palabras, si \[ P=\left[ \begin{array}{c}1/2 & 1/2 & 0\\ 1/2 & 0 & 1/2 \\0& 1/2 &1/2 \end{array} \right], \] entonces la anterior ecuación se puede escribir de la forma $x_{1}=Px_{0}$. De manera similar, $x_{2}=Px_{1}=P^{2}x_{0}$. En general, después de $k$-meses la distribución satisface que $x_{k}=Px_{k-1}=P^{2}x_{k-2}=\cdots P^{k}x_{0}$.

En general una cadena de Markov finita es un proceso evolutivo que consiste de un número finito de estados que usualmente se denotan como estado 1, estado 2, ..., estado n. En cada paso o punto en el tiempo el proceso puede estar en cualquiera de los estados o puede cambiar de estado mediante unas probabilidades fijas llamadas probabilidades de transición.
Para cada tiempo $k$ definamos el vector $x_{k}$ como el vector de probabilidades de estar en los distintos estados en el tiempo $k$, es decir, \[ x_{k}=\left[ \begin{array}{c}x_{k,1}\\ x_{k,2} \\\vdots \\ x_{k,n} \end{array} \right], \] donde $x_{k,i}$ denota la probabilidad de estar en el estado $i$-ésimo en el tiempo $k$. Los vectores $x_{k}$ son vectores de probabilidad, esto significa que $x_{k,i}\ge 0$ para $i=1,2,...,n$ y además $x_{k,1}+x_{k,2}+\cdots+x_{k,n}=1$. Denotemos a $p_{ij}$ la probabilidad de pasar del estado $j$-ésimo al estado $i$-ésimo, ests probabilidades son las entradas de una matriz $P$ que es llamada la matriz de transición de la cadena de Markov. La matriz $P$ tiene la propiedad que la suma de las entradas de cada columna es $1$, es decir, los vectores columna de $P$ son vectores de probabilidad. La regla fundamental en un proceso de Markov nos dice que el vector de probabilidades $x_{k}$ está dado por: \[ x_{k}=P^{k}x_{0}. \] Por lo tanto si conocemos la matriz de transición $P$ y el vector de estados iniciales $x_{0}$, entonces utilizando la regla anterior podemos encontrar el vector de probabilidades para cualquier tiempo.
En el ejemplo anterior \[ P=\left[ \begin{array}{c}1/2 & 1/2 & 0\\ 1/2 & 0 & 1/2 \\0& 1/2 &1/2 \end{array} \right] \text{ y } x_{0}=\left[ \begin{array}{c}100\\ 200 \\ 300 \end{array} \right]. \]

Comportamiento a largo plazo

Un aspecto interesante en una cadena de Markov es su compartamiento a largo plazo. Intuitivamente, el comportamiento a largo plazo en una cadena de Markov (en caso que este exista), es un vector de probabilidades $x$ que nos indica las probabilidades de estar en cada uno de los estados después un número grande de repeticiones. De manera formal, el comportamiento a largo plazo en una cadena de Markov (en caso que este exista) se define como \[ x=\text{Lim}_{k\to \infty}x_{k}. \] Nota: Existen cadenas de Markov que no tienen comportamiento a largo plazo definido. Sin embargo, existen condiciones que garantizan que una cadena de MArkov tenga comportamiento a largo plazo bien definido, por ejemplo, si la matriz de transición $P$ tiene todas sus entradas estrictamente positivas se puede demostrar que la cadena de Markov tiene un comportamiento a largo plazo que está bien definido y este comportamiento a largo plazo es único.

Definición: Supongamos que tenemoso una cadena de Markov con matriz de transición $P$. Decimos que un vector $x$ es un vector estacionario si $x$ es un vector de probabilidad, es decir, si sus entradas son mayores o iguales a cero y suman 1 y además $Px=x$.

Notemos que si $x$ es un vector estacionario, entonces $Px=x$, esto significa que $x$ es un vector propio de $P$ asociado al valor propio $\lambda=1$. En otras palabras, un vector estacionario es un vector propio de $P$ asociado al valor propio $\lambda=1$ que también es un vector de probabilidad.

Teorema: Si una cadena de Markov tiene comportamiento a largo plazo definido, entonces ese comportamiento a largo plazo es un vector estacionario.

Ejemplo: Consideremos el vector estacionario para el ejemplo de los camiones. Se puede demostrar que en este caso hay un comportamiento a largo plazo bien definido y por lo tanto el comportamiento a largo plazo está dado por el vector estacionario. Calculemos este comportamiento a largo plazo. En este ejemplo la matriz de transición está dada por \[ P=\left[ \begin{array}{c}1/2 & 1/2 & 0\\ 1/2 & 0 & 1/2 \\0& 1/2 &1/2 \end{array} \right] \text{ y } x_{0}=\left[ \begin{array}{c}100\\ 200 \\ 300 \end{array} \right]. \] Calculemos primero el espacio propio de $P$ asociado al valor propio $\lambda=1$. Por definición $E_{1}=Nul(P-I)$. Reduciendo la matriz $P-I$ obtenemos $\left[\begin{array}{rrr} 1&0&-1\\ 0&1&-1 \\ 0&0&0 \end{array}\right] $ así que $E_{1}$ contiene los vectores de la forma $\left[\begin{array}{r} x\\ y \\ z \end{array}\right]=\left[\begin{array}{r} z\\ z\\ z \end{array}\right]$ donde $z$ es una variable libre. Por lo tanto $E_{1}=\text{gen}\left\{ \left[\begin{array}{r} 1\\ 1 \\ 1 \end{array}\right] \right\}$. Por definición un vector estacionario $\mathbf{x}$ es un vector en $E_{1}$ que además $\mathbf{x}$ es un vector de probabilidad y por lo tanto $\mathbf{x}= \left[\begin{array}{r} z\\ z\\ z \end{array}\right]$ con $z+z+z=1$, de donde $z=\frac{1}{3}$. Luego, $\mathbf{x}= \left[\begin{array}{r} \frac{1}{3}\\ \frac{1}{3} \\ \frac{1}{3} \end{array}\right]$, es decir, la probabilidad de que a largo plazo, un camión cualquiera de la empresa se encuentre en una determinada ciudad es $\frac{1}{3}$.