Explorador de cadeias de Markov estacionárias

Simulador de matriz de transição com evolução em k passos e intuição sobre o estado estacionário.

Exemplo resolvido — Explorador de cadeias de Markov estacionárias

1	0.65985
2	0.218714
3	0.121436
Distância até a estacionaridade	0.08893

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Explorador de cadeias de Markov estacionárias

Uma distribuição é estacionária quando mais um passo não altera nada: πP = π. É um ponto fixo da matriz de transição — a cadeia continua a mover-se entre estados, mas as proporções deixam de mudar.

O que significa cada símbolo

P: a matriz de transição. O elemento na linha i, coluna j é a probabilidade de transição do estado i para o estado j, pelo que a soma de cada linha tem de ser 1 — o que a grelha acima verifica por si.
p(0): a distribuição inicial: onde a cadeia começa. O valor predefinido (1, 0, 0) significa que começa no estado 1 com certeza.
p(k): a distribuição após k passos, obtida multiplicando por P uma vez por passo.
π: a distribuição estacionária — aquela que satisfaz πP = π.
k: quantos passos dar, definidos acima. A tabela de trajetória mostra todas as distribuições desde p(0) até p(k).

De onde vem a fórmula

Escreva o que a estacionaridade exige: após um passo, a distribuição permanece inalterada, logo πP = π.
Reorganizado, isto é π(P − I) = 0 — um sistema de equações lineares, uma por cada estado. Por si só, tem infinitas soluções, pois qualquer múltiplo de uma solução também é uma solução.
Adicione a condição que a torna uma distribuição de probabilidade, Σπ = 1, e a resposta fica determinada. Para a matriz predefinida, é exatamente 8/13, 3/13, 2/13 — os valores 0.615385, 0.230769, 0.153846 apresentados acima.

Como ler o que vê

Três painéis. p(k) é onde a cadeia realmente se encontra após os seus k passos; π é para onde se dirige, juntamente com o número de iterações e a indicação de convergência; e a distância à estacionaridade mede a diferença entre eles — 0.08893 no valor predefinido k = 8, razão pela qual a nota refere que a cadeia ainda não se misturou totalmente. A tabela de trajetória abaixo mostra cada passo, a começar em (1, 0, 0).

Pressupõe: Um conjunto finito de estados e probabilidades que nunca mudam com o tempo. A soma de cada linha ser igual a 1 não é uma regra de formatação, mas sim a afirmação de que a cadeia tem de ir para algum lado em cada passo.
Falha quando: O π acima está rotulado como uma estimativa por uma razão: é obtido avançando a cadeia repetidamente — 83 iterações para a matriz predefinida — e interrompido quando as distribuições sucessivas deixam de mudar. Trata-se de uma avaliação numérica, não de uma demonstração. A resposta exata aqui é o conjunto de racionais 8/13, 3/13, 2/13, e os decimais apresentados correspondem a esses valores arredondados a seis casas decimais.

O PageRank é este mesmo cálculo, aplicado à web inteira 🖖

A distribuição estacionária não é só um exercício de livro-texto — o Google foi fundado sobre uma. Trate cada página da web como um estado e cada link como uma transição, e a distribuição estacionária dessa cadeia enorme diz com que frequência um leitor clicando em links para sempre chegaria a cada página. Isso é o PageRank. O famoso fator de amortecimento de 0,85, que manda o navegante para uma página aleatória 15% das vezes, também não é um ajuste heurístico: ele existe para garantir que todo estado possa alcançar todos os outros, que é exatamente a condição que torna a distribuição estacionária única e alcançável. Sem ele, páginas sem saída e ciclos fechados prenderiam a caminhada e quebrariam a resposta.

Para onde o longo prazo se estabiliza 🖖

Cada linha da matriz de transição é apenas um conjunto de probabilidades: se você está em um estado, com que probabilidade salta para cada um dos outros no próximo passo. Multiplique seu vetor de probabilidade atual por P uma vez por passo e os números derivam para uma mistura fixa, a distribuição estacionária π. Essa mistura indica a fração do tempo que o sistema passa em cada estado no longo prazo — experimente o exemplo do clima e observe p(k) se estabilizar.

Um alvo único que nunca alcança 🖖

Defina a matriz de dois estados como [[0,1],[1,0]] — uma moeda que sempre vira. Ela tem uma distribuição estacionária única e perfeitamente válida π = (0.5, 0.5), mas ao começar em (1, 0), p(k) oscila para sempre 1,0 → 0,1 → 1,0, sem nunca convergir. São exatamente essas cadeias periódicas que explicam por que o explorador pode indicar converged: no; a convergência garantida exige uma cadeia aperiódica, não apenas um π único.

Prática

Verifique você mesmo

Preveja primeiro a resposta e depois use os controlos acima para confirmar. Revele a solução só depois de se ter comprometido com um palpite — é isso que torna isto prática.

Por omissão a cadeia arranca com certeza no estado 1, p(0) = (1, 0, 0). Mude para (0, 0, 1) para que comece no estado 3. Preveja que leituras se mexem e quais não.

Mostrar a resposta

p(k) e a distância mexem-se; π e o número de iterações não. A partir do estado 1, oito passos chegam a 0.659852, 0.218714, 0.121436, uma distância de 0.08893. A partir do estado 3 chegam a 0.522304, 0.255274, 0.222421, uma distância de 0.18616 — mais longe, porque o estado 3 é o destino mais raro. Nos dois casos π indica 0.615385, 0.230769, 0.153846 após as mesmas 83 iterações. O ponto de partida decide o quanto a cadeia já andou, nunca para onde vai: em πP = π só aparece a matriz.
Volte a (1, 0, 0) e aumente agora o número de passos. Ao fim de quantos é que a distância à estacionaridade indica 0 — e terá a cadeia chegado?

Mostrar a resposta

Com k = 80 aparece 0, e não, não chegou. Já em k = 40 a distância é 0.000024; as seis casas decimais que o painel imprime esgotam-se simplesmente antes da diferença. Esta cadeia aproxima-se de π geometricamente e nunca lá chega num número finito de passos, pelo que o 0 é o arredondamento do ecrã — a mesma razão por que o próprio π é rotulado como estimativa. Compare com k = 8, onde a distância é 0.08893 e a nota ainda diz que a cadeia não misturou.

Problema resolvido na íntegra

Oito passos de uma cadeia de três estados iniciada no estado 1 5 passos
Uma cadeia de três estados iniciada inteiramente no estado 1, executada durante oito passos. Determine para onde se está a dirigir e quanto ainda lhe falta percorrer.
1. Um passo é um produto vetor-matriz: a probabilidade de estar no estado j a seguir é a soma sobre i de estar em i agora e de transitar i → j.
  
  $p_{k + 1} = p_{k} P, p_{0} = (1, 0, 0)$
2. Oito passos disso dão a distribuição que o painel apresenta. O estado 1 ainda detém dois terços da probabilidade, o que é muito tendo em conta que a cadeia começou ali com certeza.
  
  $p_{8} = (0.65985, 0.218714, 0.121436)$
3. O destino é a distribuição estacionária — aquela que um passo deixa inalterada. Resolver πP = π com a soma das probabilidades igual a 1 dá frações exatas, oitavos e treze avos, e não decimais.
  
  $π P = π, \sum π_{i} = 1 ⟹ π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) = (0.615385, 0.230769, 0.153846)$
4. Comparar as duas dá a distância que o painel indica, e não é pequena: após oito passos, a cadeia ainda está a cerca de 0,089 de distância no total.
  
  $∥ p_{8} - π ∥_{1} = 0.04447 + 0.01206 + 0.03241 = 0.08893$
5. Essa diferença diminui geometricamente, regida pelo segundo maior valor próprio de P. O decaimento geométrico significa que se reduz para metade num número fixo de passos e nunca atinge o zero num número finito de passos.
  
  $the gap shrinks like ∣ λ_{2} ∣^{k} — geometric, never zero$
Resposta

A ferramenta apresenta 0,65985, 0,218714, 0,121436 após oito passos, ainda a 0,08893 da estacionariedade. A distribuição estacionária é exatamente (8/13, 3/13, 2/13), e o facto que vale a pena reter é que esta não depende de onde se começou: essas mesmas três frações são o limite a partir de qualquer distribuição inicial, o que faz delas uma propriedade da matriz de transição e não desta execução em particular. Essa independência é o que torna as distribuições estacionárias úteis: o PageRank, a amostragem MCMC e a ocupação de filas de espera dependem todos de a resposta a longo prazo ser uma propriedade exclusiva das regras de transição. Apenas o tempo necessário para lá chegar depende do ponto de partida.

$π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) is where it goes, and p_{0} does not matter$

Referências (1)

The stationary distribution put to work on the whole web, damping factor and all: S. Brin & L. Page, “The anatomy of a large-scale hypertextual Web search engine.” Computer Networks and ISDN Systems 30, 107–117, 1998.

Pela equipa 42Math · Atualizado 2026-07-26

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Matemática →

Problemas de exemplo

cadeia ergódica de 3 estados - Oito passos decorridos e a leitura ainda indica uma distância L1 de 0,08893. A distribuição estacionária onde estabiliza — 0,615385, 0,230769, 0,153846 — corresponde exatamente a 8/13, 3/13 e 2/13: uma matriz escrita em décimos tem um ponto fixo em treze avos, uma vez que π surge da resolução de πP = π e não diretamente dos dados introduzidos.
clima, 2 estados - 0,666667 e 0,333333, e numa cadeia de dois estados nunca é necessário iterar para as obter. π corresponde às duas probabilidades fora da diagonal trocadas e normalizadas: 0,4 / (0,2 + 0,4) = 2/3. A partir de uma base de 50/50, dez passos chegam a 0,000035 desse valor.
cadeia de 3 estados com mistura lenta - Trinta passos resultam aqui numa distância L1 de 0,081995 — mais longe da estacionariedade do que a cadeia meteorológica chegou em dez, por um fator superior a dois mil. A causa está na diagonal: 0,97, 0,94, 0,96, pelo que a cadeia quase nunca abandona o seu estado. Exigiu 493 iterações de potência face às 25 da cadeia meteorológica, e π é 4/11, 4/11, 3/11.