Uma jogadora de basquete acerta 3 dos seus 4 primeiros lances livres. Qual é a taxa real de acerto p dela? O teorema de Bayes responde com uma distribuição inteira para p, a posteriori. Escrevê-la é fácil a menos de um número, a constante que a faz somar 1, e esse número é justamente o que fica impossível de calcular quando há muitas incógnitas. O algoritmo de Metropolis contorna isso com a ferramenta dos capítulos anteriores: ele monta uma cadeia de Markov cuja distribuição estacionária é a posteriori, usando só razões, nas quais a constante se cancela.
Ao final você vai conseguir
- Escrever a posteriori de uma probabilidade como priori vezes verossimilhança, a menos de uma constante.
- Restringir a incógnita a uma grade e achar o peso a posteriori de cada valor da grade.
- Montar a matriz de transição da cadeia de Metropolis com propostas aos vizinhos.
- Provar com o balanço detalhado que a distribuição estacionária dela é a posteriori.
- Resolver πP = π para a cadeia e calcular a média a posteriori a partir dela.
Um resumo rápido do capítulo Verossimilhança, priori beta e atualização bayesiana, que constrói cada peça com calma. Antes dos dados, uma densidade a priori f(p), aqui uma beta, diz o que acreditamos sobre p. Os dados são y sucessos em n tentativas independentes; a probabilidade deles, lida como função de p, é a verossimilhança. A regra de Bayes multiplica as duas e reescala: o novo peso de cada valor é o peso antigo vezes o quanto ele explica bem os dados, dividido pelo total.
Só o núcleo importa
Com uma priori Beta(a, b), f(p) = p^(a−1)(1 − p)^(b−1)/B(a, b). Multiplique pela verossimilhança e descarte todo fator que não contém p: B(a, b), o coeficiente binomial C(n, y) e o denominador são todos constantes. O que sobra é o núcleo da posteriori; chame-o de g. A posteriori é g dividido pelo seu próprio total.
Para trabalhar com números em vez de uma curva, deixe p assumir só alguns valores, uma grade p₁ < p₂ < … < pₘ. A posteriori na grade dá a cada valor o peso g(pₖ), reescalado para somar 1. Para a jogadora na grade {1/4, 1/2, 3/4}:
Com três pontos na grade a soma é trivial. Com dez parâmetros desconhecidos e uma grade de 100 valores para cada um, ela teria 100¹⁰ = 10²⁰ termos, mais do que qualquer computador consegue somar. Já razões como g(3/4)/g(1/2) = 81/64 são sempre baratas. O Metropolis não precisa de mais nada.
A cadeia caminha na grade. A partir do ponto atual pᵢ, um passo é:
- Proponha um vizinho: pᵢ₋₁ ou pᵢ₊₁, cada um com probabilidade ½.
- Se a proposta cair fora da grade (à esquerda de p₁ ou à direita de pₘ), rejeite: fique em pᵢ.
- Senão, aceite com probabilidade min(1, g(pⱼ)/g(pᵢ)): sempre, se o novo ponto for pelo menos tão plausível, e às vezes, se for menos. Se não aceitar, fique em pᵢ.
A cadeia dos lances livres
| de ↓ para → | 1/4 | 1/2 | 3/4 |
|---|---|---|---|
| 1/4 | 1/2 | 1/2 | 0 |
| 1/2 | 9/128 | 55/128 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
O capítulo de cadeias de Markov mostrou que um passeio entre vizinhos satisfaz o balanço detalhado no estado estacionário: o fluxo por cada aresta é o mesmo nos dois sentidos. O Metropolis é construído para que o próprio g equilibre cada aresta. Essa é a prova inteira:
Resolvendo πP = π e a média a posteriori
| 1/4 | 1/2 | 1/2 | 0 |
| 1/2 | 9/128 | 55/128 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
π = (9/154, 32/77, 81/154)
g(p) = p^(a−1+y) (1 − p)^(b−1+n−y) é o núcleo da priori vezes a verossimilhança; a cadeia só usa razões de g. As barras são a distribuição estacionária da cadeia, obtida resolvendo πP = π (exatamente, em frações, para até 9 pontos): é a posteriori na grade, sem nunca dividir g pela sua soma. Aperte play: o caminhante propõe um vizinho, uma seta verde é um movimento aceito, uma vermelha uma rejeição (ele fica e aquele ponto é contado de novo). Subidas são sempre aceitas; descidas só às vezes. Use o rápido e veja os pontos assentarem nas barras.
Num problema grande ninguém escreve P. A cadeia é simulada: comece em qualquer lugar, dê muitos passos e tire a média do que quiser sobre os valores visitados. A média de longo prazo de uma cadeia de Markov é igual à média sob π (o resultado ergódico do capítulo de cadeias de Markov), então a média dos p visitados tende à média a posteriori. Rodar bem uma cadeia (um p contínuo, propostas desiguais, aquecimento, tamanho do passo e taxa de aceitação) é o assunto do capítulo de Metropolis-Hastings.
| Passo | O que fazer |
|---|---|
| 1 | Núcleo: g(p) = p^(a−1+y)(1 − p)^(b−1+n−y). Descarte toda constante. |
| 2 | Calcule g em cada ponto da grade; se quiser, reescale para números inteiros (só as razões importam). |
| 3 | Entradas dos vizinhos: P_ij = ½ min(1, gⱼ/gᵢ). Diagonal: 1 menos o resto (ela guarda o ½ de fora da grade nas pontas). |
| 4 | Confira que cada linha soma 1. |
| 5 | Resolva πP = π com Σπ = 1; num passeio entre vizinhos, equilibre cada aresta: πᵢPᵢⱼ = πⱼPⱼᵢ. |
| 6 | Média a posteriori: Σ pₖ π(pₖ). Conferência: π deve ser proporcional a g. |
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
| Errado | Certo | Por quê |
|---|---|---|
| P_ij = g_j/g_i | ½ · min(1, g_j/g_i) | a chance ½ da proposta vem primeiro, e uma razão maior que 1 não é probabilidade |
| linhas que não somam 1 | ponha o resto em P_ii | rejeições e propostas fora da grade significam ficar |
| na ponta, propor sempre o ponto de dentro | propor para fora com ½ e ficar | propostas desiguais quebram o balanço detalhado e mudam a distribuição estacionária |
| manter C(n, y) e B(a, b) | descarte-os | eles se cancelam em toda razão; só o núcleo importa |
| média a posteriori = o ponto mais visitado | Σ pₖ π(pₖ) | a média é uma média ponderada, não a moda |
Ideias-chave
- Posteriori ∝ priori × verossimilhança; com uma priori Beta(a, b) e y de n, g(p) = p^(a−1+y)(1 − p)^(b−1+n−y).
- A constante de normalização é um número só; ela se cancela em toda razão g(pⱼ)/g(pᵢ).
- Metropolis com propostas aos vizinhos: P_ij = ½ min(1, g_j/g_i) para j = i ± 1; ficar recebe o resto, incluindo as propostas fora da grade.
- g_i P_ij = ½ min(g_i, g_j) = g_j P_ji: balanço detalhado, então a posteriori é a distribuição estacionária.
- Resolva πP = π (ou rode a cadeia); a média a posteriori é Σ pₖ π(pₖ).
- Cadeias simuladas precisam de aquecimento e de muitos passos, porque valores sucessivos são correlacionados.