Cadenas de Markov en tiempo discreto

Condiciones

• Considérese un sistema que puede estar en cualquiera de varios estados.
• El conjunto de estados es denominado el espacio de estados S y se supondrá en general que S = {0, 1, 2, ..., N}.
• Supóngase ahora que una \emph{partícula} es libre de saltar entre los estados del espacio de estados S. Su localización al tiempo t es X_t.
• De esta forma se tiene un proceso estocástico $\{X_t{\}}_{t=0}^{\mathrm{\infty }}$.
• La localización X_t se mide solamente en los tiempos discretos t = 0, 1, 2, ....
• X₀ es la localización en el tiempo* 0*.

Suposiciones

Propiedad de Markov

Suponga que la partícula está en el estado i en el tiempo t. La probabilidad que brinque a otro estado j depende solamente de i. Matemáticamente, sea i, j, i_{t-1}, ..., i₀ ∈ S. Entonces para cualquier tiempo $t$:

$$\begin{array}{rl}& P(X_{t+1}=j\mid X_t=i,X_{t-1}=i_{t-1},\dots ,X_0=i_0)\\ & =P(X_{t+1}=j\mid X_t=i)\end{array}$$

Es decir, el futuro (tiempo t+1), dado el presente (tiempo t), es independiente del pasado (tiempos t-1, ..., 0). La probabilidad anterior es la probabilidad de transición o de salto del estado i al estado j.

Las probabilidades de transición descritas son:

• Independientes de los estados pasados una vez que se conoce donde la partícula está ahora.
• Independientes de t el momento en que hace la transición.

Homogeneidad en Tiempo

$$P(X_{t+1}=j\mid X_t=i)={\mathrm{\Pi }}_{i,j}$$

Π_{i, j} es la probabilidad de transición del estado i al estado j

Cadena de Markov de tiempo discreto homogénea

Consiste de una partícula que salta en cada unidad de tiempo entre estados en un espacio de estados S. X_t denota el estado ocupado en el tiempo t para t = 0, 1, 2, ...

Si la partícula está en el estado i al tiempo t, estará en el estado j en el tiempo t+1 (sin importar los estados ocupados antes del tiempo t) con probabilidad

$${\mathrm{\Pi }}_{i,j}=P(X_{t+1}=j\mid X_t=i)$$

Cadena de Markov de tiempo discreto

Sea S = {0, 1} con probabilidades de transición dadas por:

$${\mathrm{\Pi }}_{0,0}=1/3{\mathrm{\Pi }}_{0,1}=2/3{\mathrm{\Pi }}_{1,0}=1/4{\mathrm{\Pi }}_{1,1}=3/4$$

Su representación gráfica es:

También se suele representar la misma información dada en la ecuación

$${\mathrm{\Pi }}_{0,0}=1/3{\mathrm{\Pi }}_{0,1}=2/3{\mathrm{\Pi }}_{1,0}=1/4{\mathrm{\Pi }}_{1,1}=3/4$$

pero de forma matricial:

$$\mathrm{\Pi }=\left[\begin{array}{ll}1/3& 2/3\\ 1/4& 3/4\end{array}\right]$$

Hay una manera estándar de escribir las probabilidades de salto Π_{i, j} como una matriz, a la que se le llama la matriz de transición Π. El elemento en su i-ésima fila y j-ésima columna es Π_{i, j}, la probabilidad que la partícula salte de i a j.

$$\mathrm{\Pi }=\left[\begin{array}{ccccc}{\mathrm{\Pi }}_{0,0}& {\mathrm{\Pi }}_{0,1}& {\mathrm{\Pi }}_{0,2}& \cdots & {\mathrm{\Pi }}_{0,N}\\ {\mathrm{\Pi }}_{1,0}& {\mathrm{\Pi }}_{1,1}& {\mathrm{\Pi }}_{1,2}& \cdots & {\mathrm{\Pi }}_{1,N}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\mathrm{\Pi }}_{N,0}& {\mathrm{\Pi }}_{N,1}& {\mathrm{\Pi }}_{N,2}& \cdots & {\mathrm{\Pi }}_{N,N}\end{array}\right]$$

Nótese que la i-esima fila de la matriz Π muestra las probabilidades de salto del estado i, la j-ésima columna muestra las probabilidades de salto al estado j.

Matriz de transición

Sea Π una matriz de transición de una cadena de Markov. Entonces,

• 0 \leq Π_{i, j} \leq 1 para todo i, j en el espacio de estados S.
• Π tiene filas que suman 1:

$$\sum _{j=0}^N{\mathrm{\Pi }}_{i,j}=\sum _{j=0}^{N}P(X_{t+1}=j\mid X_t=i)=1$$

Cadena de Markov de tres estados

Cadena de Markov de tiempo discreto

En una cadena de Markov hay tres estados: S = {0, 1, 2}. Del estado 0 la partícula salta a los estados 1 o 2 con una idéntica probabilidad de 1/2. Del estado 2, la partícula debe saltar al estado 1. El estado 1 es absorbente: una vez que la partícula entre al estado 1, no puede salirse. Dibuje el diagrama y escriba la matriz de transición.

$$\mathrm{\Pi }=\left[\begin{array}{ccc}0& 1/2& 1/2\\ 0& 1& 0\\ 0& 1& 0\end{array}\right]$$

Su representación gráfica es:

Estado absorbente

El estado i es absorbente si Π_{i, j} = 1.

Interpretado como ``la probabilidad de pasar del estado i al mismo estado i es del 100 %''.

Un paseo aleatorio sobre S = {0, 1, 2, ..., N}

De cualquiera de los estados interiores 1, 2, ..., N-1, la partícula salta a la derecha al estado i+1 con probabilidad p y hacia la izquierda al estado i-1 con probabilidad q = 1 - p. Es decir, para $1\le i\le N-1$,

$${\mathrm{\Pi }}_{i,i+1}=p,{\mathrm{\Pi }}_{i,i-1}=q,{\mathrm{\Pi }}_{i,j}=0\text{ para }j\ne i\pm 1$$

¿Cuál es la matriz de transición y el diagrama de saltos?

Esto corresponde al siguiente juego: tire una moneda; si sale escudo, entonces gana un colón; si sale corona, entonces pierde un colón. En cada tiro se salta al estado i+1 con probabilidad p o al estado i-1 con probabilidad q, con i colones al presente. A este ``juego'' se le conoce como la ruina del apostador.

Pueden considerarse tres casos diferentes acerca de la conducta de la partícula en los estados frontera 0 y N.

Caso 1: Ambos estados frontera podrían ser absorbentes, en cuyo caso se tendría,

$${\mathrm{\Pi }}_{0,0}=1{\mathrm{\Pi }}_{N,N}=1$$$$\mathrm{\Pi }=\left[\begin{array}{cccccccc}1& 0& 0& 0& \cdot & \cdot & \cdot & 0\\ q& 0& p& 0& \cdot & \cdot & \cdot & 0\\ 0& q& 0& p& \cdot & \cdot & \cdot & 0\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 0& 0& 0& 0& \cdot & q& 0& p\\ 0& 0& 0& 0& \cdot & \cdot & \cdot & 1\end{array}\right]$$

Esto corresponde a las situaciones en que el juego acabó dado que se quedó sin dinero o si se ha ganado el dinero de los oponentes.

Caso 2: Ambos estados frontera podrían ser reflectores, en cuyo caso se tendría,

$${\mathrm{\Pi }}_{0,1}=1{\mathrm{\Pi }}_{N,N-1}=1$$

Esto corresponde al caso cuando mi oponente me da uno de sus colones cuando quedo con los bolsillos vacíos, o inversamente. Y que siga el juego.

Caso 3: Los estados frontera podrían ser parcialmente reflectores, en cuyo caso se tendría,

$${\mathrm{\Pi }}_{0,0}=r,{\mathrm{\Pi }}_{0,1}=1-r,{\mathrm{\Pi }}_{N,N}=s,{\mathrm{\Pi }}_{N,N-1}=1-s$$

La correspondiente matriz de transición estaría dada por

$$\mathrm{\Pi }=\left[\begin{array}{ccccccccc}r& 1-r& 0& 0& 0& \cdot & \cdot & \cdot & 0\\ q& 0& p& 0& 0& \cdot & \cdot & \cdot & 0\\ 0& q& 0& p& 0& \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 0& 0& 0& 0& 0& \cdot & q& 0& p\\ 0& 0& 0& 0& 0& \cdot & \cdot & 1-s& s\end{array}\right]$$

El caso 3 incluye los dos casos anteriores para valores particulares de r y s.

Proceso de renovación

Considérese un componente cuya edad puede ser 0 o 1 o 2 ...

• Edad 0 significa acabado de instalar. Supóngase que no importa qué tan viejo el componente es, se estropeará durante el próximo intervalo de tiempo con probabilidad q o continuará operando con probabilidad p = 1 - q. Así, el componente sigue la propiedad de la carencia de memoria.
• El espacio de estados es S = {0, 1, 2, ...} y el estado del sistema es la edad del componente instalado. Suponga que tan pronto como el componente se averíe, es reemplazado instantáneamente y entonces el estado del sistema se vuelve cero. La transición del estado 0 al estado 0 ocurre si el componente recién instalado se avería inmediatamente.

$$\mathrm{\Pi }=\left[\begin{array}{ccccccc}q& p& 0& 0& \cdot & \cdot & \cdot \\ q& 0& p& 0& 0& \cdot & \cdot \\ 0& q& 0& p& 0& \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \end{array}\right]$$

• Véase que el espacio de estados S, en este caso, si bien discreto, tiene infinitamente muchos estados.
• Este modelo recibe también el nombre de modelo de nacimiento o de desastre. Algunas aplicaciones son evidentes: tiempos de vida de componentes. Hay una que no es tan obvia: las noticias se apilan en una pizarra de avisos a una razón más o menos constante hasta que alguien decide tirarlas todas.
• El estado del sistema es el número de días desde la última vez que la pizarra fue limpiada. Si la limpieza de la pizarra se hace aleatoriamente, independiente de cuantas noticias haya o del tiempo desde la última limpieza, la pizarra será limpiada en la próxima unidad de tiempo con una probabilidad constante q.

La matriz de transición de orden $t$

La matriz de transición $\mathrm{\Pi }$ muestra las probabilidades de transición ${\mathrm{\Pi }}_{i,j}$. Supóngase que se necesita encontrar probabilidades tales como:

$$P(X_{t+3}=j\mid X_t=i)$$

de que la partícula estará en estado $j$ tres saltos desde el estado actual $i$.

Si las probabilidades de transición de un paso ${\mathrm{\Pi }}_{i,j}$ son las entradas de la matriz $\mathrm{\Pi }$, ¿cómo puede encontrarse las probabilidades de tres pasos, y más generalmente, las probabilidades de $t$ pasos?

Matriz de transición de orden $t$

La matriz de transición de orden $t$ es ${\mathrm{\Pi }}^t$, cuya entrada $(i,j)$ es:

$${\mathrm{\Pi }}_{i,j}^t=P(X_t=j\mid X_0=i)$$

que es la probabilidad de saltar de $i$ a $j$ en $t$ pasos.

La homogeneidad en el tiempo (el hecho de que las probabilidades de transición no dependan de $t$) implica que, no obstante el tiempo $\mu \ge 0$:

$$P(X_{t+\mu }=j\mid X_{\mu }=i)={\mathrm{\Pi }}_{i,j}^t$$

O sea, las probabilidades de transición de $t$ pasos dependen solamente de la diferencia de tiempo.

Visualización de la transición de estados

Un algoritmo general se necesita para hallar la matriz de transición ${\mathrm{\Pi }}^t$ de orden $t$ para cualquier matriz $\mathrm{\Pi }$ de una cadena de Markov dada.

Para hallar la matriz de transición de orden $t+1$ a partir de la de orden $t$, se usan las suposiciones de Markov básicas.

• Supóngase que la partícula empieza en estado $i$ en el tiempo 0, es decir, $X_0=i$.
• Para que la partícula esté en el estado $j$ en el tiempo $t+1$, debe haber atravesado algún estado $k$ en el tiempo intermedio $t$, es decir, $X_0=i⟶X_t=k⟶X_{t+1}=j$.

El objetivo es encontrar una expresión para ${\mathrm{\Pi }}_{i,j}^{t+1}$.

$$\begin{array}{rl}{\mathrm{\Pi }}_{i,j}^{t+1}& =P(X_{t+1}=j\mid X_0=i)\\ & =\sum _{k=0}^{N}P(X_{t+1}=j\text{ y }{X}_t=k\mid X_0=i)\\ & =\sum _{k=0}^{N}P(X_{t+1}=j\mid X_t=k\text{ y }{X}_0=i)P(X_t=k\mid X_0=i)\\ & =\sum _{k=0}^{N}P(X_{t+1}=j\mid X_t=k)P(X_t=k\mid X_0=i)\\ & =\sum _{k=0}^N{\mathrm{\Pi }}_{i,k}^t{\mathrm{\Pi }}_{k,j}\end{array}$$

• La primera igualdad es por definición de la matriz de transición de orden $t$.
• La segunda igualdad viene de particionar donde la partícula estaba en el tiempo $t$.
• La tercera igualdad viene de la regla de probabilidad condicional:$$P(A\cap B\mid C)=P(A\mid B\cap C)P(B\mid C)$$
• La cuarta igualdad usa la propiedad de Markov, donde la probabilidad de transición solo depende del estado anterior.
• La quinta igualdad se obtiene por definición de las matrices de transición y por la propiedad de homogeneidad.

WARNING

Falta la transcripción de 5_20_3_markov_discreto.md