4.6. Processos de Markov

Como vimos anteriormente, Processos de Markov, também chamados de cadeias de Markov, são processos estocásticos em que a mudança de estado para um estado futuro, conhecendo-se o estado atual, não depende dos estados passados. Mais precisamente, se \(\{X_t\}_{t\in I}\) é um processo aleatório, \(t_1 < t_2 < \ldots < t_n < t_{n+1}\) pertencem a \(I\), e \(E, E_1, \ldots, E_n\) são possíveis eventos, então, dados \(X_{t_1} \in E_1, X_{t_2} \in E_2, \ldots, X_{t_n} in E_n\), temos que a probabilidade de \(X_{t_{n+1}} \in E\) só depende da informação dada no instante mais recente \(t_n\), ou seja

\[ \mathbb{P}(X_{t_{n+1}} \in E | X_{t_1} \in E_1, X_{t_2} \in E_2, \ldots, X_{t_n} \in E_n) = \mathbb{P}(X_{t_{n+1}} \in E | X_{t_n} \in E_n). \]

No caso em que o conjunto de eventos é discreto, podemos escrever

\[ \mathbb{P}(X_{t_{n+1}} = x | X_{t_1} = x_1, X_{t_2} = x_2, \ldots, X_{t_n} = x_n) = \mathbb{P}(X_{t_{n+1}} = x | X_{t_n} = x_n). \]

Processos de Markov são chamados de sem memória. Processos de Markov podem ser contínuos ou discretos e o espaço de estados também pode ser contínuo ou discreto.

O processo de Bernoulli é um exemplo trivial de uma cadeia de Markov discreta. O passeio aleatório é outro exemplo. O modelo de Einstein para o movimento Browniano, por sua vez, é um exemplo de um processo de Markov contínuo. Já o modelo da urna sem recomposição, como tratado anteriormente, não é uma cadeia de Markov, já que cada passo depende do estado do sistema em todos os passos anteriores.

Revisitando o problema da urna

Conforme formulado inicialmente, o problema da urna não é uma cadeia de Markov. Mas podemos modelar o problema de outra forma, para que seja uma cadeia de Markov. Lembramos que começamos com \(N\) bolinhas de cada cor. Podemos denotar por \(X_n\) o total de bolinhas vermelhas retiradas da urna até o passo \(n\), inclusive. Para o passo \(n + 1\), só há duas possibilidades: \(X_{n + 1} = X_n + 1\), caso uma bolinha vermelha seja retirada, ou \(X_{n + 1} = X_n\), caso a bolinha retirada seja da cor preta. Todos os outros estados tem probabilidade nula de ocorrer.

Observe que, inicialmente, temos um total de \(2N\) bolinhas. Após \(n\) retiradas, sobram \(2N - n\) bolinhas. Por sua vez, inicialmente temos \(N\) bolinhas de cada cor. Após retirarmos \(X_n\) bolinhas vermelhas, temos \(N - X_n\) vermelhas restantes. As outras \((2N - n) - (N - X_n) = N - n + X_n\) são bolinhas pretas. Assim, podemos expressar as probabilidades de cada uma das duas realizações possíveis na forma

\[ \mathbb{P}(X_{n + 1} = X_n + 1) = \frac{N - X_n}{2N - n}, \]

e

\[ \mathbb{P}(X_{n + 1} = X_n + 1) = \frac{N - n + X_n}{2N - n}. \]

Probabilidades de transição

Quando temos um número discreto de estados possíveis, podemos determinar a evolução do processo em termos das probabilidades do sistema ir de um estado \(i\), no instante \(n\), para um estado \(j\), no instante \(n+1\). Isso nos leva a definir as probabilidades de transição

\[ p_{ij}^n = \mathbb{P}(X_{n+1} = j | X_n = i). \]

O processo é temporalmente homogêneo quando as probabilidades de transição são independentes do parâmetro, i.e. \(p_{ij}^n = p_{ij}\) independe de \(n\).

Quando o conjunto de possíveis estados é finito, isso nos dá uma matriz de transição,

\[ P_n = (p_{ij}^n). \]

Observe que cada linha da matriz de transição deve ter soma igual a

\[ \sum_j p_{ij} = 1, \qquad \forall j. \]

No caso de um processo de Bernoulli com estados \(\{1, 0\}\) (e.g. sucesso e fracasso) ocorrendo com probabilidades \(p\) e \(1 - p\), respectivamente, temos a matriz de transição

\[ P_n = P = \left[ \begin{matrix} p & 1 - p \\ p & 1 - p \end{matrix} \right]. \]

No caso de um objeto poder ser colocado em uma de duas possíveis posições, digamos \(1\) e \(2\), e que jogamos uma moeda viciada para decidir se objeto troca de posição, com probabilidade \(p\), e se mantém na posição, com probabilidade \(1 - p\), então a matriz de transição é

\[ P_n = P = \left[ \begin{matrix} p & 1 - p \\ 1 - p & p \end{matrix} \right]. \]

No caso do passeio aleatório, temos um espaço de estados enumerável, \(\Omega = \mathbb{Z}\), e as probabilidades de transição são

\[ p_{ij} = \mathbb{P}(X_{n+1} = j | X_n = i) = \begin{cases} 1/2, & j = i \pm 1, \\ 0, & \text{caso contrário} \end{cases}. \]

Previsão ingênua de tempo

Vamos imaginar, agora, um problema de previsão de tempo, em que classificamos o tempo em três estados: "ensolarado", "nublado" e "chuvoso". Seja \(X_n\) o estado do sistema no \(n\)-ésimo dia, com \(1\), \(2\) e \(3\) indicando cada um desses possíveis estados, respectivamente.

Vamos assumir que, a partir de uma "análise criteriosa do histórico do clima em uma determinada região e uma determinada época", observamos que, em média, após um dia ensolarado, temos 70% de chances de termos outro dia ensolarado, 20% de termos um dia nublado e 10% de termos um dia chuvoso. Após um dia nublado, as chances são de 30%, 40%, 30%, respectivamente. E após um dia chuvoso, as chances são de 20%, 40% e 40%.

Como temos um número finito de estados e as probabilidades de transição são estacionárias, podemos definir a matriz de transição de estados \(P = (p_{ij})_{ij}\) por

\[ p_{ij} = \mathbb{P}(X_{n+1} = j | X_n = i) \]

No nosso caso, temos

\[ P = \left[ \begin{matrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.4 & 0.4 \end{matrix} \right] \]

Sabendo-se a distribuição de probabilidades representadas por um vetor linha \(X_n \sim w = [p1, p2, p3]\), \(p_i \geq 0\), \(p_1 + p_2 + p_3 = 1\) no instante \(n\), as probabilidades no instante \(X_{n + 1}\) são dadas por

\[ X_{n + 1} \sim w P = ( P^t w^t)^t. \]

Previsões de longo prazo podem ser feitas iterando-se a matriz de transição:

\[ X_{n+k} \sim wP^k, \quad k = 1, 2, \ldots. \]

Por exemplo, se em determinado momento \(n\) temos \(X_n = 1\), ou seja, temos um dia ensolarado, representado pelo vetor probabilidade \(w = [1, 0, 0]\), então daqui a dois dias teremos

\[ X_{n+2} \sim w P^2 = \left( \left[ \begin{matrix} 0.57 & 0.39 & 0.17 \\ 0.26 & 0.44 & 0.36 \\ 0.17 & 0.27 & 0.3 \end{matrix} \right] \left(\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}\right) \right)^t = \left(\begin{matrix} 0.57 \\ 0.26 \\ 0.17 \end{matrix}\right)^t = [0.57, 0.26, 0.17], \]

ou seja, \(57\%\) de termos um dia ensolarado, \(13\%\) de termos um dia nublado e \(17\%\) de termos um dia chuvoso.

Distribuições estacionárias de processos temporalmente homogêneos

No caso de um processo temporalmente homogêneo em um espaço de eventos finito \(\{1, \ldots, J\}\), a matriz de transição \(P\) é independente do parâmetro temporal. Além disso, como as linhas somam \(1\), a matriz tem necessariamente um autovalor igual a \(1\), com autovetor com todos os coeficientes iguais a \(1\). De fato,

\[ P \left(\begin{matrix} 1 \\ \vdots \\ 1 \end{matrix}\right) = \left(\begin{matrix} \sum_{j=1}^J p_{1j} \\ \vdots \\ \sum_{j=1}^J p_{Jj} \end{matrix}\right) = \left(\begin{matrix} 1 \\ \vdots \\ 1 \end{matrix}\right), \]

Em particular, \(\det(P - I) = 0\), portanto \(\det(P^t - I) = \det(P - I) = 0\) e \(P^t\) também possui um autovalor igual a \(1\).

Isso implica na existência de (pelo menos) um vetor linha \(v=[v_1, \ldots, v_J]\) tal que \(v^t\) seja um autovetor de \(P^t\) associado ao autovalor \(1\) e com norma \(1\), i.e. \(P^t v^t = v^t\), ou seja

\[ vP = v, \]

e tal que \(v_1 + \ldots + v_J = 1\). Isso nos dá uma distribuição estacionária

\[ \mathbb{P}(X_n = i) = v_i. \]

Por exemplo, no caso da previsão ingênua de tempo,

\[ P^t = \left[ \begin{matrix} 0.7 & 0.3 & 0.2 \\ 0.2 & 0.4 & 0.4 \\ 0.1 & 0.3 & 0.4 \end{matrix} \right] \]

Os autovalores são aproximadamente \(0.0438\), \(0.4562\) e \(1\). O autoespaço associado ao autovalor \(1\) é

\[ V_1 = \{(6s, 4s, 3s); \;s\in \mathbb{R}\}. \]

O autovalor com elementos não negativos e com norma \(1\) é

\[ v = \frac{1}{13}[6, 4, 3] \approx [0.4615, 0.3077, 0.2308]. \]

Assim, a distribuição com probabilidades de aproximadamente \(46,15\%\) de sol, \(30,77\%\) de nuvens e \(23,08\%\) de chuva é uma distribuição estacionária. (Ela está associada a média de dias ensolarados, nublados e chuvosos coletados para a análise). Ou seja, se em um determinado dia essas são as probabilidades para a previsão para o dia seguinte, então as previsões a longo prazo serão iguais a essa. Podemos interpretar \(v\) como sendo essa lei de distribuição de probabilidades.

Como, nesse caso, há um único autovalor igual a \(1\) e os outros dois são estritamente menores do que \(1\), então a previsão "assintótica" é igual a essa obtida pela análise de autovalores: \(\lim_{k\rightarrow \infty} wP^{n + k} \sim v\).

Além de, necessariamente, ter um autovalor igual a \(1\), qualquer matriz de transição tem autovalores com valor absoluto entre \(0\) e \(1\), mas eles podem ser negativos ou complexos.

Exercícios

1. Qualquer matriz cujos elementos sejam não negativos e cujas linhas tenham soma igual a \(1\) define um processo de Markov. Tais matrizes são chamadas de matrizes de Markov. Encontre os autovalores das seguintes matrizes de Markov, observando que podemos ter (a) autovalores nulos; (b) autovalores negativos; (c) mais de um autovalor igual a \(1\); e (d) autovalores complexos conjugados:

\[ \textrm{(a) } P = \left[ \begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix} \right], \qquad \textrm{(b) } P = \left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] \] \[ \textrm{(c) } P = \left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right], \qquad \textrm{(d) } P = \left[ \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{matrix} \right] \]

2. Mostre que quando \(1\) é o único autovalor com valor absoluto igual a \(1\), de uma matriz de Markov \(P\), então \(uP^k\) converge para um autovetor associado a esse autovalor. Se o autoespaço desse autovalor tiver dimensão um, então esse limite independe do vetor inicial \(u\), desde que ele esteja associada a uma distribuição de probabilidades, ou seja, que seja um vetor com norma \(1\).

3. Encontre os autoespaços associados aos autovalores das matrizes (c) e (d) do exercício acima, obtenha as distribuições de probabilidade associadas a esses autovalores e observe que existem distribuições cíclicas, ou seja, que se repetem após dois ou mais passos.

4. Sejá \(P\) é a matriz de transição de uma cadeia de Markov discreta em \(I = \mathbb{N}\) e temporalmente homogênea, com um número finito \(J\) de estados possíveis. Seja \(v = (v_j)_{j = 1, \ldots, J}\) uma distribuição inicial de probabilidades para o processo. Mostre que cada \(vP^n\) é uma distribuição de probabilidades, i.e. \(0 \leq (vP_n)_j \leq 1\) e \(\sum_j (vP^n)_j = 1\), para cada \(n\in \mathbb{N}\), e que não pode haver autovalor da matriz de transição com módulo maior do que \(1\).