Cadeias de Markov de Tempo Discreto

Uma cadeia de Markov de tempo discreto é uma sequência de estados aleatórios que evoluem em tempo inteiro, de modo que a distribuição do próximo estado depende apenas do estado atual, e não de todo o passado.

Definition

Uma cadeia de Markov de tempo discreto é um processo estocástico em um espaço de estados contável indexado pelos inteiros não negativos, cuja distribuição condicional do próximo estado, dado todo o histórico, depende apenas do estado presente, codificada por uma matriz de probabilidade de transição de um passo.

Scope

Esta área abrange a propriedade de Markov e as matrizes de transição, a classificação de estados por comunicação, recorrência, transitoriedade e periodicidade, a existência e unicidade de distribuições estacionárias e limitantes, taxas de convergência e mistura, e as principais aplicações, incluindo Monte Carlo via cadeia de Markov e modelos ocultos de Markov.

Sub-topics

• Hidden Markov Models
• Markov Chain Classification and Recurrence
• Markov Chain Monte Carlo
• Stationary Distributions and Convergence

Core questions

• O que significa a propriedade de Markov e como ela é capturada por uma matriz de transição?
• Como os estados são classificados em classes recorrentes, transientes e periódicas?
• Quando uma cadeia possui uma distribuição estacionária única e converge para ela?
• Quão rápido uma cadeia se aproxima do equilíbrio e como isso é explorado na simulação?

Key theories

Propriedade de Markov e equações de Chapman-Kolmogorov

O futuro é condicionalmente independente do passado dado o presente, de modo que as probabilidades de transição de múltiplos passos são obtidas multiplicando matrizes de transição, o que torna o comportamento em n passos computável a partir da matriz de um passo.

Teorema ergódico para cadeias de Markov

Uma cadeia irredutível, aperiódica e positivamente recorrente possui uma distribuição estacionária única para a qual a distribuição marginal converge e contra a qual as médias temporais das funções convergem quase certamente, ligando as frequências de longo prazo à lei estacionária.

Clinical relevance

As cadeias de Markov de tempo discreto modelam passeios aleatórios, instantâneos de filas, genética populacional, algoritmos de classificação como o PageRank e transições de estados econômicos; sua teoria de convergência sustenta o método de Monte Carlo via cadeia de Markov, o método computacional dominante para amostragem de distribuições de probabilidade complexas em estatística, física e aprendizado de máquina.

History

Andrey Markov introduziu cadeias com transições dependentes, mas sem memória, em 1906, para estender a lei dos grandes números além da independência, ilustrando-as com sequências de letras na poesia de Pushkin. Kolmogorov e Doeblin estabeleceram a teoria da convergência em bases rigorosas de teoria da medida na década de 1930.

Key figures

• Andrey Markov
• Andrey Kolmogorov
• Wolfgang Doeblin

Seminal works

• norris1997

Frequently asked questions

O que torna um processo uma cadeia de Markov?

A propriedade de Markov: dado o estado presente, a evolução futura é independente de como a cadeia atingiu esse estado, de modo que toda a dinâmica é descrita por probabilidades de transição de um passo.

Quando uma cadeia de Markov converge para uma distribuição única de longo prazo?

Quando é irredutível, aperiódica e positivamente recorrente; então existe uma única distribuição estacionária para a qual a cadeia converge, independentemente do seu estado inicial.