Álgebra linear · Cadeia de Markov

Cadeia de Markov

Numa cadeia de Markov, o estado muda aleatoriamente e as probabilidades do próximo estado dependem apenas do atual. Com a matriz de transição P, a distribuição de amanhã é a de hoje multiplicada por P. A repetição conduz muitas vezes a uma distribuição estacionária π com πP = π, vetor próprio à esquerda de valor próprio 1.

Cadeia de Markov nesta visualização

Numa cadeia de Markov, as probabilidades do próximo estado dependem apenas do atual. Aqui há sol, nuvens e chuva. A linha ii da matriz de transição PP contém as probabilidades de amanhã se o estado de hoje for ii. Cada linha é um vetor de probabilidades. Se a distribuição de hoje é o vetor linha pp, a de amanhã é pPpP e a de daqui a nn dias é pn=p0Pnp_n = p_0 P^n. Com três estados, cada distribuição é um ponto de um triângulo: cada vértice representa um estado certo e as probabilidades são os pesos dos vértices. Os pontos escuros são as linhas de PP, o azul é o início e o percurso vermelho liga p0,p1,p2,…p_0, p_1, p_2, \dots.

O que acontece num passo

Cada vértice passa, num passo, para a respetiva linha: a um dia em que há sol com certeza segue-se a distribuição da primeira linha. Qualquer distribuição pp é uma média ponderada dos vértices, pelo que pPpP é a mesma média das linhas. O triângulo passa para o triângulo das linhas e, em dois passos, para o das linhas de P2P^2. Quando alguma potência de PP tem todas as entradas positivas, estes triângulos encaixados contraem-se num ponto: a distribuição estacionária π\pi.

Porque é π um vetor próprio e a que ritmo se aproxima pₙ?

O ponto fixo satisfaz πP=π\pi P = \pi: π\pi é um vetor próprio à esquerda de valor próprio 1 (em colunas, PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). As entradas da diferença p0−πp_0 - \pi somam 0. Nesse subespaço, PP tem os outros dois valores próprios λ2,λ3\lambda_2, \lambda_3. Em cada direção própria, um passo multiplica o vetor pelo valor próprio associado. Se ambos os módulos forem inferiores a 1, pnp_n tende para π\pi e o maior módulo ∣λ2∣|\lambda_2| determina o ritmo. Para o tempo, ∣λ2∣≈0.462|\lambda_2| \approx 0.462: quando nn é grande, fica pouco menos de metade da distância por passo, se o início tiver uma componente na direção de λ2\lambda_2. Com valores próprios complexos, o percurso também roda enquanto se contrai.

Quando não há convergência

No ciclo sucedem-se sol, nuvens e chuva. Os outros dois valores próprios têm módulo 1 e pnp_n continua a circular, salvo se começar em π\pi. Com dois estados absorventes, sol e chuva persistem, o valor próprio 1 é duplo e qualquer mistura dos dois fica fixa. Assim pnp_n converge, mas o limite depende do início. Numa cadeia finita, pnp_n tende para o mesmo π\pi a partir de qualquer início se e só se existir uma única classe fechada de estados comunicantes e esta for aperiódica. Dentro da classe todos os estados são mutuamente acessíveis, sem saída para o exterior. Basta, por exemplo, que alguma potência PmP^m tenha todas as entradas positivas.

Aspetos a observar

  • Seja qual for o início, a distribuição estacionária dá as probabilidades do tempo num dia distante. O tempo continua a mudar de dia para dia.
  • Com mais de três estados, as distribuições preenchem um simplexo, o análogo do triângulo numa dimensão superior. O argumento é o mesmo.

Controlos

  • Arraste um ponto escuro para mudar uma linha da matriz ou o azul para mudar o início. As setas deslocam o ponto com foco uma centésima.

Conceitos relacionados