Cadeias de Markov

Uma cadeia de Markov modela um sistema que evolui aleatoriamente e cujo futuro depende apenas do estado atual, não de como se chegou até ele. Essa hipótese de "ausência de memória" é forte, mas cobre uma quantidade surpreendente de fenômenos.

Definição

Um processo $(X_0, X_1, \dots)$ sobre um conjunto de estados satisfaz a propriedade de Markov quando

$$P(X_{n+1}=j \mid X_n=i, X_{n-1}=\dots) = P(X_{n+1}=j \mid X_n=i) = p_{ij}$$

A matriz de transição $P$ reúne as probabilidades $p_{ij}$. Cada linha soma 1 — é uma matriz estocástica.

Evolução

Se $\pi_0$ é a distribuição inicial (vetor linha), então

$$\pi_n = \pi_0 P^n$$

A potência da matriz governa o comportamento no tempo — e é aqui que a diagonalização mostra seu valor: $P^n = VD^nV^{-1}$ torna o cálculo tratável e revela que o segundo maior autovalor controla a velocidade de convergência.

A entrada $(i,j)$ de $P^n$ é a probabilidade de estar em $j$ após $n$ passos partindo de $i$.

Distribuição estacionária

Um vetor $\pi$ é estacionário quando

$$\pi P = \pi, \qquad \sum_i \pi_i = 1$$

É um autovetor à esquerda com autovalor 1 — que sempre existe para matriz estocástica.

Interpretação: se a cadeia começa em $\pi$, permanece em $\pi$. E, sob condições adequadas, converge para $\pi$ a partir de qualquer início.

Ergodicidade

A convergência exige duas propriedades:

• Irredutível: é possível ir de qualquer estado a qualquer outro.
• Aperiódica: não há ciclo forçado de período fixo.

Uma cadeia irredutível e aperiódica sobre estados finitos é ergódica, e então a distribuição estacionária é única e $\pi_n \to \pi$ independentemente de $\pi_0$.

Falhas dessas hipóteses têm consequência concreta. Uma cadeia redutível pode ficar presa numa componente — é o problema dos "sumidouros" na web, em que uma página sem links de saída absorve toda a massa de probabilidade. A solução do PageRank é o fator de amortecimento: com probabilidade $1-d$, saltar para uma página aleatória. Isso torna a cadeia irredutível e aperiódica por construção.

$$\pi = d,\pi P + \frac{1-d}{n}\mathbf{1}, \qquad d \approx 0{,}85$$

Tempo de mistura

Quanto tempo até a distribuição ficar próxima da estacionária? O tempo de mistura é

$$t_{\text{mix}}(\varepsilon) = \min{n : |\pi_n - \pi|_{TV} \le \varepsilon}$$

Ele é governado pelo hiato espectral $1 - |\lambda_2|$: quanto maior o hiato, mais rápida a mistura. Cadeias com hiato pequeno misturam devagar — o que costuma acontecer quando o espaço de estados tem "gargalos" entre regiões.

Este é o parâmetro que decide se um método MCMC é utilizável na prática: uma cadeia que mistura devagar produz amostras correlacionadas e estimativas ruins, por mais que se rode.

Cadeias reversíveis

Uma cadeia satisfaz equilíbrio detalhado quando

$$\pi_i p_{ij} = \pi_j p_{ji}$$

Essa condição implica que $\pi$ é estacionária, e é bem mais fácil de verificar que a definição. É por isso que os algoritmos de MCMC são construídos para satisfazê-la: em vez de calcular $\pi$, constrói-se uma cadeia que a tem como estacionária.

O algoritmo de Metropolis-Hastings faz exatamente isso: propõe um movimento e o aceita com probabilidade

$$\alpha = \min\left(1, \frac{\pi(j)q(j\to i)}{\pi(i)q(i\to j)}\right)$$

O ponto genial é que $\pi$ só aparece como razão — a constante de normalização, tipicamente intratável, se cancela. É isso que permite amostrar de distribuições a posteriori que não se sabe calcular.

Exemplo trabalhado

Duas páginas, A e B. De A vai-se a B com probabilidade 1; de B, volta-se a A com probabilidade $0{,}5$ e fica-se em B com $0{,}5$.

$$P = \begin{pmatrix} 0 & 1 \ 0{,}5 & 0{,}5 \end{pmatrix}$$

Resolvendo $\pi P = \pi$ com $\pi = (\pi_A, \pi_B)$:

$$\pi_A = 0{,}5,\pi_B, \qquad \pi_A + \pi_B = 1$$

Logo $\pi_B = 2/3$ e $\pi_A = 1/3$. No longo prazo, dois terços do tempo em B.

Note que a cadeia é aperiódica graças ao laço em B; sem ele, ela alternaria com período 2 e não convergiria.

Aplicações em computação

PageRank. A pontuação é a distribuição estacionária do passeio aleatório na web, calculada pelo método da potência.

MCMC. Inferência bayesiana quando a posteriori não tem forma fechada: Metropolis-Hastings, amostrador de Gibbs, Monte Carlo Hamiltoniano.

Modelos ocultos de Markov. Reconhecimento de fala, etiquetagem morfossintática, bioinformática. Os algoritmos forward-backward e de Viterbi são programação dinâmica sobre a cadeia.

Filas. Modelos de fila e de disponibilidade de sistemas são cadeias de Markov de tempo contínuo.

Aprendizado por reforço. Processos de decisão de Markov acrescentam ações e recompensas; a equação de Bellman é a versão com decisão da equação estacionária.

Geração de texto. Cadeias de Markov sobre $n$-gramas foram o modelo de linguagem padrão antes das redes neurais, e continuam úteis como linha de base.

Erros comuns

• Supor convergência sem verificar irredutibilidade e aperiodicidade.
• Confundir a matriz de transição com sua transposta. A convenção (linhas ou colunas somando 1) varia entre textos e bibliotecas.
• Rodar MCMC sem descarte inicial e sem diagnosticar convergência.
• Ignorar o tempo de mistura e tratar amostras correlacionadas como independentes.
• Aplicar a propriedade de Markov onde o histórico claramente importa.

Leituras recomendadas

• Norris, Markov Chains — tratamento rigoroso e acessível.
• Levin, Peres e Wilmer, Markov Chains and Mixing Times — a referência moderna sobre tempo de mistura; gratuito no site dos autores.
• Mitzenmacher e Upfal, capítulos 7 e 10 — cadeias de Markov e MCMC aplicados a computação.
• Documentação do Stan e do PyMC — MCMC na prática, com diagnósticos de convergência.

James R. Norris (1997). Markov Chains. Cambridge University Press. DOI: 10.1017/cbo9780511810633. David A. Levin and Yuval Peres and Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times. American Mathematical Society. DOI: 10.1090/mbk/107. Michael Mitzenmacher and Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press. ISBN 9781107154889.

Referências

1. James R. Norris (1997). Markov Chains. Cambridge University Press.
2. David A. Levin; Yuval Peres; Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times. American Mathematical Society.
3. Michael Mitzenmacher; Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press.