Configurações
Ações
Opções de Exibição
Editor de Matriz de Transição
Cada linha deve somar 1.0 (matriz estocástica)
Distribuição de Probabilidade
Convergência para Distribuição Estacionária
Análise Matemática
Distribuição Atual p_t
Distribuição Estacionária π
π satisfaz π = πP
Autovalores de P
λ₁ = 1 é garantido para matrizes estocásticas
Propriedades da Cadeia
Estimativa de Tempo de Mistura
Passos para alcançar distância ε = 0.01 de π
Distância de Variação Total
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
O que é uma Cadeia de Markov?
Uma cadeia de Markov é um processo estocástico com a propriedade sem memória: o estado futuro depende apenas do estado atual, não da sequência de eventos que o precederam.
Propriedade de Markov
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
Fórmula de Transição
p_{t+1} = p_t P
onde p_t é o vetor de distribuição no tempo t, e P é a matriz de transição
Conceitos Chave
- Espaço de Estados S: O conjunto de todos os estados possíveis
- Matriz de Transição P: P[i][j] = P(X_{t+1}=j | X_t=i)
- Matriz Estocástica: Cada linha soma 1.0
- Probabilidade de Caminho: Produto das probabilidades de transição ao longo do caminho
Distribuição Estacionária π
Uma distribuição estacionária π é uma distribuição de probabilidade que permanece inalterada na cadeia de Markov: uma vez que o sistema atinge π, ele permanece lá para sempre.
Equação Estacionária
π = πP
ou equivalentemente: π(P - I) = 0
Interpretação de Autovetor Esquerdo
π é o autovetor esquerdo de P correspondente ao autovalor 1
πP = λπ where λ = 1
Existência e Unicidade
- Existência: Toda cadeia de Markov finita tem pelo menos uma distribuição estacionária
- Unicidade: Garantida para cadeias irredutíveis (todos os estados se comunicam)
- Perron-Frobenius: Para cadeias regulares, π tem todas as entradas positivas
Distância de Variação Total
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Mede o quão perto a distribuição atual está da estacionária
Propriedades de Convergência
Sob que condições uma cadeia de Markov converge para sua distribuição estacionária?
Tipos de Cadeia
- Regular (Aperiódica + Irredutível): Converge para um π único de qualquer distribuição inicial
- Periódica: Os estados ciclam através de um padrão periódico
- Redutível: Contém estados absorventes ou múltiplas classes comunicantes
Taxa de Convergência
Determinada pelo segundo maior autovalor em magnitude (SLEM):
|p_t - π| ≈ C × |λ_2|^t
Lacuna espectral = 1 - |λ₂|, lacuna maior = convergência mais rápida
Tempo de Mistura
Tempo para ficar ε próximo da distribuição estacionária:
t_mix(ε) = log(ε) / log(|λ_2|)
Detecção de Periodicidade
Um estado tem período d se todos os ciclos desse estado têm comprimentos divisíveis por d
- Aperiódica: d = 1 (pode retornar a qualquer momento)
- Periódica: d > 1 (ciclos estão sincronizados)
Balanceamento Detalhado (Cadeias Reversíveis)
π(i)P(i,j) = π(j)P(j,i)
Uma condição suficiente para π ser estacionária
Aplicações do Mundo Real
Algoritmo PageRank
O PageRank do Google modela a navegação web como uma caminhada aleatória. A distribuição estacionária dá a importância de cada página.
P = (1-d)M + d(1/n)J
M: matriz de links, d: fator de amortecimento, J: matriz de uns
Caminhadas Aleatórias em Grafos
Usado em análise de redes, sistemas de recomendação e amostragem de grafos. A distribuição estacionária está relacionada aos graus dos nós.
Métodos de Amostragem MCMC
Métodos de Monte Carlo por Cadeias de Markov geram amostras de distribuições de probabilidade complexas construindo cadeias com o alvo como distribuição estacionária.
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
Modelos Ocultos de Markov (HMM)
Usados em reconhecimento de fala, bioinformática e finanças. HMMs têm uma cadeia de Markov subjacente com estados ocultos.
Teoria de Filas
Processos de nascimento-morte modelam filas. A distribuição estacionária dá a probabilidade de longo prazo de ter n clientes no sistema.
Jogos de Tabuleiro
Jogos como Monopoly e Cobras e Escadas podem ser modelados como cadeias de Markov para calcular a duração esperada do jogo e frequências de visita.