Cadeias de Markov
Uma cadeia de Markov modela um sistema que se move entre um conjunto de estados ao longo do tempo, em que a probabilidade de passar para o próximo estado depende apenas do estado atual, não de como o sistema chegou até lá. Essa propriedade de “sem memória do passado” torna as cadeias de Markov um dos modelos mais simples e úteis de processos aleatórios que evoluem no tempo, e ela se apoia diretamente nos experimentos aleatórios vistos antes nesta seção.
A propriedade de Markov
Para uma sequência de estados \(X_0, X_1, X_2, \ldots\), a propriedade de Markov diz:
\[P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)\]
Tudo o que é relevante sobre o futuro já está capturado pelo estado presente. Todo o histórico passado não acrescenta nada além disso, uma vez que você sabe onde o sistema está agora.
A matriz de transição
Reúna as probabilidades de transição em um passo \(p_{ij} = P(X_{n+1}=j \mid X_n=i)\) em uma matriz \(P\). Cada linha de \(P\) deve somar 1: a partir do estado \(i\), o sistema tem que ir para algum lugar, possivelmente permanecendo em \(i\).
Exemplo resolvido: um modelo meteorológico simples
Um sistema de dois estados é o lugar mais simples para ver a matriz de transição e a distribuição estacionária de longo prazo em ação.
Dois estados, Ensolarado e Chuvoso. Se hoje está ensolarado, amanhã estará ensolarado com probabilidade 0,8 e chuvoso com probabilidade 0,2. Se hoje está chuvoso, amanhã estará ensolarado com probabilidade 0,4 e chuvoso com probabilidade 0,6. A matriz de transição (linhas e colunas ordenadas Ensolarado, Chuvoso):
\[P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}\]
Partindo de um dia ensolarado ($X_0 = $ Ensolarado, então a distribuição inicial é \((1, 0)\)), encontre a distribuição de probabilidade ao longo dos próximos dias multiplicando repetidamente por \(P\).
Dia 1: \((1,0) \cdot P = (0{,}8,\ 0{,}2)\).
Dia 2: \((0{,}8, 0{,}2) \cdot P = (0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}4,\ \ 0{,}8 \times 0{,}2 + 0{,}2 \times 0{,}6) = (0{,}64+0{,}08,\ \ 0{,}16+0{,}12) = (0{,}72,\ 0{,}28)\).
Dia 3: \((0{,}72, 0{,}28) \cdot P = (0{,}688,\ 0{,}312)\).
Assim, a probabilidade de um dia ensolarado é \(0{,}8 \to 0{,}72 \to 0{,}688\), diminuindo lentamente dia a dia, mesmo que hoje fosse garantidamente ensolarado.
A distribuição estacionária
Conforme \(n \to \infty\), a distribuição sobre os estados se estabiliza em uma distribuição fixa de longo prazo \(\pi\) que não muda mais de um passo para o outro.
\[\pi P = \pi, \qquad \sum_i \pi_i = 1\]
\(\pi\) é um autovetor à esquerda de \(P\) com autovalor 1, normalizado para que suas entradas somem 1.
Para o exemplo meteorológico, a distribuição estacionária é \(\pi = (2/3,\ 1/3) = (0{,}6667,\ 0{,}3333)\): a longo prazo, cerca de dois terços dos dias são ensolarados e um terço chuvosos, independentemente de qual seja o tempo hoje. Isso corresponde à tendência já visível na sequência dia a dia acima: \(0{,}8 \to 0{,}72 \to 0{,}688\) está convergindo lentamente para \(0{,}6667\).
A probabilidade de um dia ensolarado decai de forma suave e monotônica de 1 em direção ao valor estacionário \(2/3\), independentemente de o dia 0 ter sido garantidamente ensolarado.
Encontrando a distribuição estacionária em R
Resolver \(\pi P = \pi\) equivale a encontrar o autovetor à esquerda de \(P\) associado ao autovalor 1 (equivalentemente, o autovetor de \(P^T\) para o autovalor 1), e depois normalizá-lo para que some 1.
⚠️ Uma distribuição estacionária só existe, e é única, sob certas condições
Nem toda cadeia de Markov tem uma distribuição estacionária única. Isso exige que a cadeia seja irredutível (todo estado alcançável a partir de qualquer outro) e aperiódica (ela não cicla entre estados em um padrão rígido e previsível). O exemplo meteorológico satisfaz ambas trivialmente: você pode alcançar qualquer estado a partir de qualquer outro, e não há ciclo forçado. Mas cadeias com estados absorventes (um estado em que se pode entrar, mas nunca sair) ou cadeias que alternam estritamente entre estados em um ciclo fixo podem não convergir para uma única distribuição estacionária, ou podem ter uma, mas nunca realmente alcançá-la a partir de todo ponto de partida.
Onde as cadeias de Markov aparecem
A matemática abstrata fundamenta uma gama surpreendente de aplicações reais:
- PageRank do Google: páginas da web como estados, links como transições, a distribuição estacionária classifica a importância das páginas.
- Markov Chain Monte Carlo (MCMC): usado amplamente na computação bayesiana para amostrar distribuições posteriores complexas.
- Geração de texto e autocompletar: probabilidades de transição de palavra para palavra (ou de caractere para caractere).
- Jogos de tabuleiro e modelos de fila: mudanças de posição guiadas por dados, clientes chegando e saindo de uma fila.
- Genética: modelagem de sequências de nucleotídeos ao longo de uma fita de DNA.
Executando isso em R
O modelo meteorológico acima, suas transições em múltiplos passos e sua distribuição estacionária vêm todos de um punhado de operações com matrizes:
P <- matrix(c(0.8, 0.2,
0.4, 0.6), nrow = 2, byrow = TRUE)
rownames(P) <- colnames(P) <- c("Sunny", "Rainy")
# n-step transition: probability distribution after n days starting Sunny
library(expm)
p0 <- c(1, 0)
p0 %*% (P %^% 3)
# Stationary distribution via eigenvectors
ev <- eigen(t(P))
pi_vec <- Re(ev$vectors[, which(abs(ev$values - 1) < 1e-8)])
pi_vec / sum(pi_vec)
# Simulate a random walk through the chain
library(markovchain)
mc <- new("markovchain", states = c("Sunny","Rainy"), transitionMatrix = P)
rmarkovchain(n = 20, object = mc, t0 = "Sunny")💡 Como ler uma matriz de transição rapidamente
As linhas são “de”, as colunas são “para”, e cada linha deve somar exatamente 1, uma verificação rápida ao construir ou inspecionar manualmente uma matriz de transição. Os elementos da diagonal \(p_{ii}\) indicam o quão “pegajoso” é um estado: qual a probabilidade de o sistema permanecer onde está em vez de transicionar. No exemplo meteorológico, Ensolarado é mais pegajoso (0,8) do que Chuvoso (0,6), e é exatamente por isso que a distribuição estacionária de longo prazo favorece os dias ensolarados.
