Cadeias de Markov

O espaço de estados de uma cadeia de Markov, denotado por \[ \mathcal{S} = \{ s_1, s_2, s_3, \ldots \}, \] é o conjunto de valores que $X_n$ pode assumir.

Uma cadeia de Markov é dita ser homogênea se a probabilidade condicional \[ \Pr \big[ X_{n+1} = s_i \mid X_n = s_j \big] \] é independente do tempo $n$. Nesse caso, adota-se a notação $p_{i \mid j}$ para a probabilidade acima.

Os seguintes parâmetros especificam completamente uma cadeia de Markov homogênea com espaço de estados finito $\mathcal{S} = \{ s_1, s_2, \ldots, s_r \}$:

1. A PMF inicial \[ \vec{p}_0 = \Big[ \Pr[X_0 = s_1] ~~ \Pr[X_0 = s_2] ~~ \cdots ~~ \Pr[X_0 = s_r] \Big], \] que é um vetor de probabilidade de dimensão $1 \times r$.
2. A matriz de transição \[ P = \begin{bmatrix} p_{1 \mid 1} & p_{2 \mid 1} & \cdots & p_{r \mid 1} \\ p_{1 \mid 2} & p_{2 \mid 2} & \cdots & p_{r \mid 2} \\ \vdots & \vdots & \ddots & \vdots \\ p_{1 \mid r} & p_{2 \mid r} & \cdots & p_{r \mid r} \end{bmatrix}, \] que é uma matriz estocástica de dimensão $r \times r$.

Na Terra de Oz, o dia pode ser ensolarado ($\mathsf{S}$), chuvoso ($\mathsf{C}$) ou com neve ($\mathsf{N}$). O tempo obedece às seguintes regras:

• O dia da criação foi ensolarado.
• Nunca há dois dias ensolarados em seguida. Mais precisamente, se o dia atual é ensolarado, então o dia seguinte será chuvoso ou com neve, com igual probabilidade.
• Se o dia atual é chuvoso ou com neve, então: Em metade dos casos, o dia seguinte permanecerá igual; Na outra metade dos casos, há mudança para algum outro estado, com igual probabilidade.

Definindo o espaço de estados como $\mathcal{S} = \{ \mathsf{C}, \mathsf{S}, \mathsf{N} \}$, temos que a PMF inicial e a matriz de transição são, respectivamente, \[ \vec{p}_0 = \left[ \begin{array}{ccc} \mathsf{C} & \mathsf{S} & \mathsf{N} \\ \hline 0 & 1 & 0 \\ \end{array} \right] \] e \[ P = \left[ \begin{array}{c|ccc} ~ & \mathsf{C} & \mathsf{S} & \mathsf{N} \\ \hline \mathsf{C} & 1/2 & 1/4 & 1/4 \\ \mathsf{S} & 1/2 & 0 & 1/2 \\ \mathsf{N} & 1/4 & 1/4 & 1/2 \\ \end{array} \right]. \] O diagrama de estados da cadeia é mostrado abaixo.

Seja $\vec{p}_0$ a PMF inicial e $P$ a matriz de transição de uma cadeia de Markov. Então, o vetor $\vec{p}_n$ que representa a PMF de $X_n$ é dado por \vec{p}_n = \vec{p}_{n-1} P = \vec{p}_0 P^n. Demonstração.

Na Terra de Oz, a PMF de $X_6$ é \[ \vec{p}_6 = \vec{p}_0 P^6 = \big[ 0 ~~ 1 ~~ 0 \big] \begin{bmatrix} 1/2 & 1/4 & 1/4 \\ 1/2 & 0 & 1/2 \\ 1/4 & 1/4 & 1/2 \end{bmatrix}^6 = \big[ 0{,}3999 ~~~ 0{,}2002 ~~~ 0{,}3999 \big]. \]

Um vetor de probabilidade $\vec{\pi}$ é dito ser um vetor de equilíbrio de uma cadeia de Markov se \[ \vec{\pi} P = \vec{\pi}. \]

Todo vetor de equilíbrio $\vec{\pi}$ deve satisfazer \[ \begin{cases} \vec{\pi} \, (P - I) & = \vec{0} \\[1ex] \vec{\pi} \, \vec{1}^\top & = 1, \end{cases} \] onde $\vec{0} = \big[ 0 ~~ 0 ~~ \cdots ~~ 0 \big]$, $\vec{1} = \big[ 1 ~~ 1 ~~ \cdots ~~ 1 \big]$ e $I$ é a matriz identidade $r \times r$.

Um vetor de equilíbrio $\vec{\pi} = [\pi_1 ~ \pi_2 ~ \pi_3]$ da Terra de Oz deve satisfazer \[ \begin{cases} \big[ \pi_1 ~~ \pi_2 ~~ \pi_3 \big] \begin{bmatrix} -1/2 & 1/4 & 1/4 \\ 1/2 & -1 & 1/2 \\ 1/4 & 1/4 & -1/2 \end{bmatrix} & = \big[ 0 ~~~ 0 ~~~ 0 \big] \\[6ex] \big[ \pi_1 ~~ \pi_2 ~~ \pi_3 \big] \begin{bmatrix} ~ 1 ~ \\ ~ 1 ~ \\ ~ 1 ~ \end{bmatrix} & = 1, \end{cases} \] ou, equivalentemente, \[ \begin{cases} -(1/2) \, \pi_1 ~ + ~ (1/2) \, \pi_2 ~ + ~ (1/4) \, \pi_3 ~ = ~ 0 \\ \phantom{+}(1/4) \, \pi_1 ~ - ~ \phantom{(1/1)} \, \pi_2 ~ + ~ (1/4) \, \pi_3 ~ = ~ 0 \\ \phantom{+}(1/4) \, \pi_1 ~ + ~ (1/2) \, \pi_2 ~ - ~ (1/2) \, \pi_3 ~ = ~ 0 \\ \phantom{+(1/1)} \, \pi_1 ~ + ~ \phantom{(1/1)} \, \pi_2 ~ + ~ \phantom{(1/1)} \, \pi_3 ~ = ~ 1. \end{cases} \] Este sistema de equações lineares possui uma única solução: $\vec{\pi} = [2/5 ~~~ 1/5 ~~~ 2/5]$.

Uma matriz de transição $P$ é dita ser regular se alguma potência $P^k$ possui todos os elementos estritamente positivos.

A matriz de transição da Terra de Oz é regular, pois \[ P^2 = \begin{bmatrix} 1/2 & 1/4 & 1/4 \\ 1/2 & 0 & 1/2 \\ 1/4 & 1/4 & 1/2 \end{bmatrix}^2 = \begin{bmatrix} 7/16 & 3/16 & 3/8 \\ 3/8 & 1/4 & 3/8 \\ 3/8 & 3/16 & 7/16 \end{bmatrix}. \]

Toda cadeia de Markov com matriz de transição regular possui um único vetor de equilíbrio $\vec{\pi}$. Além disso, \[ \lim_{n \to \infty} \vec{p}_n = \vec{\pi}, \] qualquer que seja a PMF inicial $\vec{p}_0$.

Um estado $s_i$ é dito ser absorvente se $p_{i \mid i} = 1$. Em outras palavras, uma vez que a cadeia alcança o estado $s_i$, nunca mais sai desse estado. Um estado é dito ser transiente se não for absorvente.

Uma cadeia de Markov é dita ser absorvente se possuir pelo menos um estado absorvente; além disso, qualquer estado absorvente da cadeia deve ser alcançável a partir qualquer estado transiente.

Um bêbado caminha em uma avenida com quatro blocos. Quando ele se encontra em algum cruzamento ($\mathsf{C}_1$, $\mathsf{C}_2$ ou $\mathsf{C}_3$), ele anda para esquerda ou para a direita, com igual probabilidade. Se ele chegar em casa ($\mathsf{H}$) ou no bar ($\mathsf{B}$), ele permanecerá lá para sempre.
Espaço de estados: \[ \mathcal{S} = \{ \mathsf{H}, \mathsf{C}_1, \mathsf{C}_2, \mathsf{C}_3, \mathsf{B} \}. \] Diagrama de estados: Matriz de transição: \[ P = \left[ \begin{array}{c|ccccc} ~ & \mathsf{H} & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 & \mathsf{B} \\ \hline \mathsf{H} & 1 & 0 & 0 & 0 & 0 \\ \mathsf{C}_1 & 1/2 & 0 & 1/2 & 0 & 0 \\ \mathsf{C}_2 & 0 & 1/2 & 0 & 1/2 & 0 \\ \mathsf{C}_3 & 0 & 0 & 1/2 & 0 & 1/2 \\ \mathsf{B} & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right]. \] Os estados $\mathsf{H}$ e $\mathsf{B}$ são absorventes. Os estados $\mathsf{C}_1$, $\mathsf{C}_2$ e $\mathsf{C}_3$ são transientes.

Em uma cadeia de Markov absorvente, o processo será absorvido com probabilidade $1$.

Reordene os estados:

• Primeiro: os $t$ estados transientes.
• Depois: os $r$ estados absorventes.

Após os reordenamentos, a matriz de transição \[ P = \left[ \begin{array}{c:c} Q & R \\ \hdashline 0 & I \end{array} \right] \] é dita estar no formato canônico.

A matriz de transição no formato canônico é \[ P = \left[ \begin{array}{c|ccc:cc} ~ & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 & \mathsf{H} & \mathsf{B} \\ \hline \mathsf{C}_1 & 0 & 1/2 & 0 & 1/2 & 0 \\ \mathsf{C}_2 & 1/2 & 0 & 1/2 & 0 & 0 \\ \mathsf{C}_3 & 0 & 1/2 & 0 & 0 & 1/2 \\ \hdashline \mathsf{H} & 0 & 0 & 0 & 1 & 0 \\ \mathsf{B} & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right], \] de modo que \[ Q = \left[ \begin{array}{c|ccc} ~ & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 \\ \hline \mathsf{C}_1 & 0 & 1/2 & 0 \\ \mathsf{C}_2 & 1/2 & 0 & 1/2 \\ \mathsf{C}_3 & 0 & 1/2 & 0 \\ \end{array} \right] \qquad \text{e} \qquad R = \left[ \begin{array}{c|cc} ~ & \mathsf{H} & \mathsf{B} \\ \hline \mathsf{C}_1 & 1/2 & 0 \\ \mathsf{C}_2 & 0 & 0 \\ \mathsf{C}_3 & 0 & 1/2 \\ \end{array} \right]. \]

O número médio de vezes que o processo, iniciando no estado $s_i$, transita pelo estado $s_j$ é dado pelo elemento $(i, j)$ da matriz \[ N = (I - Q)^{-1}. \]

\[ N = (I - Q)^{-1} = \begin{bmatrix} 1 & -1/2 & 0 \\ -1/2 & 1 & -1/2 \\ 0 & -1/2 & 1 \end{bmatrix}^{-1} = \left[ \begin{array}{c|ccc} ~ & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 \\ \hline \mathsf{C}_1 & 3/2 & 1 & 1/2 \\ \mathsf{C}_2 & 1 & 2 & 1 \\ \mathsf{C}_3 & 1/2 & 1 & 3/2 \end{array} \right]. \]

O tempo médio para que o processo, iniciando no estado $s_i$, seja absorvido é dado pela soma dos elementos da linha $i$ da matriz $N$. Em outras palavras, é o elemento $i$ do vetor \[ \vec{t} = N \, \vec{1}, \] onde $\vec{1} = \big[ 1 ~~ 1 ~~ \cdots ~~ 1 \big]^\top$.

\[ \vec{t} = N \begin{bmatrix} ~ 1 ~ \\ ~ 1 ~ \\ ~ 1 ~ \end{bmatrix} = \left[ \begin{array}{c|ccc} ~ & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 \\ \hline \mathsf{C}_1 & 3/2 & 1 & 1/2 \\ \mathsf{C}_2 & 1 & 2 & 1 \\ \mathsf{C}_3 & 1/2 & 1 & 3/2 \end{array} \right] \begin{bmatrix} ~ 1 ~ \\ ~ 1 ~ \\ ~ 1 ~ \end{bmatrix} = \left[ \begin{array}{c|c} \mathsf{C}_1 & 3 \\ \mathsf{C}_2 & 4 \\ \mathsf{C}_3 & 3 \\ \end{array} \right]. \]

A probabilidade de que, iniciando no estado $s_i$, o processo seja absorvido no estado $s_j$ é dada pelo elemento $(i, j)$ da matriz \[ B = NR. \]

\[ B = NR = \left[ \begin{array}{c|ccc} ~ & \mathsf{C}_1 & \mathsf{C}_2 & \mathsf{C}_3 \\ \hline \mathsf{C}_1 & 3/2 & 1 & 1/2 \\ \mathsf{C}_2 & 1 & 2 & 1 \\ \mathsf{C}_3 & 1/2 & 1 & 3/2 \end{array} \right] \left[ \begin{array}{c|cc} ~ & \mathsf{H} & \mathsf{B} \\ \hline \mathsf{C}_1 & 1/2 & 0 \\ \mathsf{C}_2 & 0 & 0 \\ \mathsf{C}_3 & 0 & 1/2 \\ \end{array} \right] = \left[ \begin{array}{c|cc} ~ & \mathsf{H} & \mathsf{B} \\ \hline \mathsf{C}_1 & 3/4 & 1/4 \\ \mathsf{C}_2 & 1/2 & 1/2 \\ \mathsf{C}_3 & 1/4 & 3/4 \\ \end{array} \right]. \]