Markov 2-Estados Estacionário

Cadeia de Markov de 2 estados — distribuição estacionária

Numa cadeia de Markov, o próximo estado depende só do estado atual, e não do caminho que levou até ali. É a propriedade sem memória. Pegue dois estados com a matriz de transição P = [[1−a, a], [b, 1−b]]. A distribuição estacionária π é aquela que não se altera sob a dinâmica, ou seja, πP = π, com π₁ + π₂ = 1. Resolva esse sistema linear e você chega a π = (b/(a+b), a/(a+b)). Com a = 0,3 e b = 0,2, por exemplo, π dá (0,4, 0,6). Comece de qualquer distribuição inicial e a cadeia se aproxima de π em O(log) iterações, com o segundo autovalor de P ditando a velocidade.

Aplicações

O PageRank do Google trata páginas web como estados. Cadeias de dois ou mais estados também aparecem na modelagem populacional (migração entre urbano e rural), na teoria de filas (sistemas M/M/1), em transições de estado de processos químicos, em PLN para geração de palavras e modelos de texto, nas frequências alélicas da genética populacional, na engenharia de confiabilidade com estados funcionando e falho, e na velha previsão do tempo do tipo sol/chuva.

Perguntas frequentes

Sempre existe distribuição estacionária? Quando a cadeia é irredutível e aperiódica (a + b > 0 e não (a = b = 1)), sim, e é única. Um caso degenerado como a = b = 0 dá uma cadeia absorvente que nunca mistura.

O que significa a distribuição estacionária? No longo prazo, é a fatia de tempo que a cadeia passa em cada estado, e ela não depende de onde você começou.

Quão rápido converge? Isso é regido por |1 − a − b|, o segundo autovalor. Quanto mais perto de 0, mais rápida a convergência.