Aplicações algorítmicas
Fase 2 — Capítulo 5 (Häggström caps. 8–10)
A pergunta operacional
A teoria de cadeias de Markov não é só descritiva — é algorítmica. Problemas computacionais podem ser reformulados como amostragem de distribuições específicas, e cadeias de Markov ad-hoc são construídas para resolvê-los. Este capítulo cobre os principais.
Simulated annealing
Para minimizar função-objetivo \(E(\mathbf{x})\) em espaço discreto grande, define-se \(\pi_T(\mathbf{x}) \propto e^{-E(\mathbf{x})/T}\). Para \(T \to 0\), \(\pi_T\) concentra no mínimo global. Algoritmo: rodar Metropolis com \(\pi_T\), baixando \(T\) gradualmente. Convergência ao mínimo global garantida sob cooling schedule logarítmico — lentos, mas teoricamente impecáveis.
Hard-core model e o problema de empacotamento
Distribuição uniforme sobre configurações independent-set de um grafo. MCMC dá amostragem aproximada; tempo de mistura controla quão rápido. Aplicações: alocação de recursos, scheduling.
PageRank
A matriz de transição do navegador aleatório na web tem estacionária \(\pi\) que é, por definição, o PageRank (Brin; Page, 1998). O algoritmo reduz o problema de ranking ao problema markoviano canônico: existe distribuição estacionária na cadeia construída sobre o grafo da web, e ela ordena as páginas pela probabilidade limite de visita. O fator de teleporte \(d \in (0,1)\) garante irredutibilidade e aperiodicidade.
Particle filters / SMC
Generalização sequencial de MCMC para inferência online em modelos de espaço de estados. Aplicações: tracking, robótica, filtragem em séries temporais.
Conexão com Ashby/Beer
Algorítmica markoviana é, em linguagem ashbyana, amplificação operacional da variedade \(H(R)\): o regulador computacional pode tratar problemas cuja variedade combinatória excederia a capacidade analítica humana. Alves et al. (2022) usa, no fundo, esquemas multi-vista que prefiguram amostragem multimodal — precursor conceitual do que MCMC formaliza.
Pergunta de verificação
Implemente simulated annealing para o Traveling Salesman em 20 cidades. Compare resultado a heurística greedy. Em linguagem cibernética: como o aparato MCMC amplifica \(H(R)\) em problema de otimização institucional?
Para Joana: classificar risco-de-evasão por perfil de estudante via posterior MCMC. O paralelo com Alves et al. (2022) é o uso da diversidade de fontes como amplificador da variedade do regulador.