Introdução e Conceitos

Como podemos prever o próximo movimento de uma partícula, o clima de amanhã ou até a página mais relevante na internet? Nesse texto falaremos sobre as Cadeias de Markov, ferramentas muito versáteis que podemos utilizar para modelar sistemas onde a próxima etapa depende apenas da situação atual, ignorando o histórico anterior. Imagine prever o clima: sabendo que hoje é ensolarado, você pode estimar a probabilidade de amanhã chover ou continuar ensolarado.

As possibilidades são vastas, mas no mundo real é possível que o exemplo mais cintilante de uma aplicação de cadeias de Markov seja o algoritmo de classificação de páginas de internet do Google: o PageRank.

Seja $X_t$ uma variável aleatória, onde $t$ é um número natural que em nosso contexto significa o tempo. Desse modo, $X_t = x$ indica que a variável aleatória $X$ assume o valor $x$ no instante $t$. Uma cadeia de Markov é um processo que se move entre os elementos de um conjunto $\Lambda$ da seguinte maneira: quando $x \in \Lambda$, a próxima posição é escolhida de acordo com uma distribuição de probabilidade fixada $P(x,\cdot)$, dependendo apenas de $x$. Precisamente, uma sequência de variáveis aleatórias $\{X_i\}_{i\geq0}$ é uma cadeia de Markov com espaço de estados $\Lambda$ e matriz de transição $P$ se para todo $x,y\in\Lambda$, todo $t\geq1$ e todo evento $H_{t-1}=\bigcap_{s=0}^{t-1}\{X_s=x_s\}$ satisfazendo $\Pr(H_{t-1}\cap\{X_t=x\})>0$, temos $$\Pr\{X_{t+1}=y|H_{t-1}\cap\{X_t=x\}\}=\Pr\{X_{t+1}=y|X_t=x\}=p_{xy}.$$

Note que o espaço de estados representa o conjunto de valores que as variáveis $X_t$ podem assumir. Basicamente, o que essa definição implica é que, para o que acontecerá no processo a partir do instante $t$, não importa o histórico $H_{t-1}$ desse processo, mas tão somente sua posição atual. Essa propriedade é tão importante para essa teoria que tem até um nome: propriedade de Markov. Mais precisamente, essa propriedade significa que a probabilidade condicional de ir do estado $x$ para o estado $y$ é a mesma, não importando os estados anteriores ao estado atual $x$.

Para uma partícula que se move segundo um processo markoviano, sua próxima posição depende apenas de sua posição atual.

Matriz e Diagrama de Transição

Uma consequência da propriedade de Markov é que uma cadeia de Markov é totalmente definida a partir de seu espaço de estados $\Lambda$ e de sua matriz de transição $P$ de dimensão $|\Lambda|\times|\Lambda|$. A matriz de transição é definida como $$P:=\{p_{ij}\}_{i,j\in\Lambda},$$ de modo que $\sum_{j\in\Lambda} p_{ij}=1$ e $p_{ij} = \Pr\{X_t=j|X_{t-1}=i\}$ é uma probabilidade de transição do estado $i$ para o estado $j$. Basicamente, a matriz de transição elenca todas as probabilidades de transição de um estado para o outro. Além disso, a soma de todos os elementos em cada linha devem ser iguais a $1$, já que são probabilidades.

Para qualquer cadeia de Markov com espaço de estados finito, podemos desenhar um diagrama de transição a partir da matriz da cadeia. Seja $X_t$ o clima na cidade do Recife em um dia qualquer que pode indicar Sol $X_n=1$ ou Chuva $X_n=2$. Sua matriz de transição tem o seguinte formato.

A partir dessa matriz, podemos elaborar um diagrama de transição.

Vemos que $p(1,1)=0.6$. Ou seja, a probabilidade de que na cidade do Recife, um dia de sol seja seguido de outro dia de sol é de $0.6$. E se quiséssemos saber a probabilidade de amanhã está chovendo dado que hoje está um dia de sol divino? A resposta é $p(1,2)=0.4$. E se quisermos saber a probabilidade de depois de amanhã estar chovendo dado que hoje faz sol? Vejamos o diagrama com mais atenção. Se hoje faz dia de sol, então amanhã pode fazer um dia de sol ou não e depois de amanhã também. Vejamos os cenários possíveis.

Pode ser que amanhã chova ou faça sol, dado que hoje temos sol. Então vemos que $$p(1,1)p(1,2)+p(1,2)p(2,2) = 0.6\cdot0.4+0.4\cdot0.8.$$ Esse resultado equivale a tomarmos o quadrado da matriz de transição $P^2=P\cdot P$ no valor da segunda coluna da primeira linha. Essa é uma importante propriedade das cadeias de Markov. Podemos fazer os cálculos das transições em vários passos à frente tomando simplesmente a potência da matriz de transição. Caso queiramos saber a probabilidade do processo estar em determinado estado em 20 espaços, basta elevar a matriz de transição à potência de $20$.

Classificação dos estados de uma cadeia de Markov

Estudar a classificação dos estados de uma cadeia é uma etapa importante no estudo desses processos. Basicamente, os estados podem ser classificados de duas maneiras, transientes ou recorrentes. Dizemos que um estado é transiente quando existe uma probabilidade positiva de que o processo, uma vez tendo visitado esse estado, não torne a visitá-lo. Precisamente, defina $T_y = \min\{t\geq1|X_t=y\}$ como o tempo de primeiro retorno a $y$ e seja $$\rho_{yy} = \Pr\{T_y<\infty|X_0=y\},$$ que é a probabilidade de $X_t$ retornar a $y$ dado que o processo começou em $y$. Sendo assim, se $\rho_{yy}<1$ então existe uma probabilidade positiva de que $T_y=\infty$ e, portanto, $y$ é estado transiente.

O estado é recorrente quando existe uma probabilidade positiva de que o processo retorne a ele em passos futuros, aliás, retorne infinitas vezes. Isso implica que $\rho_{yy}=1$ então $y$ é estado recorrente.

Dizemos que uma classe é um conjunto de estados com classificação comum. Se em uma classe de estados só temos estados transientes, a classe é dita transiente. Como uma classe só pode conter estados com uma mesma classificação, formando uma classe de equivalência, dizemos que essa classe é irredutível. Como consequência disso, se um conjunto de estados qualquer possui, por exemplo, dois estados recorrentes e um transiente, podemos formar uma classe recorrente eliminando o estado transiente. Quando uma cadeia forma uma única classe de equivalência, dizemos que ela é irredutível.

Vejamos o exemplo a seguir.

Vemos que os estados $2$ e $3$ são transientes, pois uma vez que o processo os deixe, não visitará mais esses estados. Por outro lado, o estado $1$ é recorrente, pois o processo fica saltando entre ele e o estado $5$. Portanto, a classe $\{1,5\}$ é uma classe recorrente, assim como também é recorrente a classe $\{4,6,7\}$.

Quando é possível ir de um estado $j$ para um estado $i$, dizemos que $i$ é acessível a partir de $j$ e indicamos essa relação por $j \rightarrow i$. Quando essa relação é recíproca, então dizemos que os estados $i$ e $j$ são comunicantes e escrevemos $j\leftrightarrow i$. Naturalmente, estados comunicantes formam uma classe de equivalência, como os estados recorrentes. Como $3$ é acessível por $2$, mas $2$ não é acessível por $3$, os dois não formam uma classe transiente.

Cadeias de Markov e Grafos

Um grafo não orientado $(V,\mathcal{E})$ consiste em uma coleção finita $V$ de vértices $v$ e uma coleção $\mathcal{E}$ não ordenada de pares de vértices distintos $\langle u,v\rangle$ que chamamos de arestas. Se $\langle u,v\rangle\in\mathcal{E}$ então dizemos que $u$ e $v$ são vizinhos e denotamos isso por $u\thicksim v$. O grau de um vértice $v\in\mathcal{E}$ consiste no número de arestas ligadas a ele. Em um gráfico não dirigido a relação $u\thicksim v$ é simétrica, isto é $u\thicksim v \iff v\thicksim u$.

Essencialmente, um grafo é um conjunto de pontos e de setas ligando esses pontos. No gráfico não orientado, as setas que ligam dois vértices são bidirecionais, isto é, a relação vale nos dois sentidos. Com isso, podemos usar um grafo para modelar cadeias de Markov. Por exemplo, considere um conjunto de vértices $V=\{1,2,3,4\}$ de modo que $\mathcal{E} = \{1\thicksim3,1\thicksim4, 2\thicksim4, 3\thicksim4\}$, lembre que o grafo é não orientado. A figura do grafo tem a seguinte forma.

A partir dessa figura, podemos montar um grafo orientado que representa um diagrama de uma cadeia de Markov com espaço de estados $\Lambda = \{1,2,3,4\}$. Nesse caso, seja $d_i$ o grau do $i-$ésimo vértice, ou seja, o número de arestas ligadas ao vértice $i$. Seja $p_{ij}:=1/d_i$. Por exemplo, para $i=4$ vemos que $p_{4j}=1/3$. No caso do estado $i=3$, vemos que $p_{3j} = 1/2$. Fazendo isso para todos os estados, recuperamos as probabilidades de transição. O diagrama da cadeia fica assim.

Com isso, aprendemos como usar um grafo não orientado para representar uma cadeia de Markov e como a partir do grafo podemos obter a matriz de transição, bem como o seu correspondente diagrama.

Conclusões

Neste texto, abordamos alguns dos fundamentos das cadeias de Markov, discutindo propriedades como a classificação dos estados e a formação de classes de equivalência. Também exploramos como os grafos podem ser utilizados para representar cadeias de Markov, tornando a visualização das transições entre estados mais intuitiva.

A teoria das cadeias de Markov é uma área fascinante da teoria das probabilidades, combinando simplicidade conceitual com uma vasta capacidade de modelar sistemas complexos. Suas aplicações abrangem áreas diversas, como a teoria das filas, a modelagem de dinâmicas populacionais em biologia e a análise de sistemas financeiros.

Em mecânica estatística, cadeias de Markov são adotadas na modelagem de fenômenos como os sistemas ferromagnéticos e os spin glasses, auxiliando na compreensão de comportamentos emergentes em sistemas físicos. Com tantas possibilidades, as cadeias de Markov são um verdadeiro coringa para a análise estocástica de problemas reais.

Há muitas referências disponíveis para quem deseja se aprofundar no assunto. O livro texto do momento para o estudo de cadeias de Markov com espaço de estados finitos é o Markov Chains and Mixing Times de Perez et. al. Uma das principais abordagens exploradas nesse livro é o uso de técnicas de acoplamento para investigar o tempo de convergência para distribuições estacionárias de cadeias. Em um nível bem mais introdutório, temos o Essencials of Stochastic Process de Durrett ou ainda o excelente texto de Brémmaud, Markov Chains Gibbs Fields, Monte Carlo Simulation and Queues.