Em estatística, a cadeia de Markov Monte Carlo (Markov chain Monte Carlo ou MCMC em inglês) é uma classe de algoritmos usados para extrair amostras de uma distribuição de probabilidade. Dada uma distribuição de probabilidade, pode-se construir uma cadeia de Markov cuja distribuição de elementos se aproxima dela – isto é, a distribuição de equilíbrio da cadeia de Markov corresponde à distribuição alvo. Quanto mais etapas forem incluídas, mais próxima a distribuição da amostra corresponderá à distribuição desejada.

Os métodos de Monte Carlo de cadeia de Markov são usados para estudar distribuições de probabilidade que são muito complexas ou muito dimensionais para serem estudadas apenas com técnicas analíticas. Existem vários algoritmos para construir tais cadeias de Markov, incluindo o algoritmo Metropolis–Hastings.

Explicação geral miniaturadaimagem| Convergência do algoritmo Metropolis–Hastings. A cadeia de Markov Monte Carlo tenta aproximar a distribuição azul com a distribuição laranja. Os métodos de Monte Carlo de cadeia de Markov criam amostras de uma variável aleatória contínua, com densidade de probabilidade proporcional a uma função conhecida. Essas amostras podem ser usadas para avaliar uma integral sobre essa variável, como seu valor esperado ou variância.

Na prática, geralmente se desenvolve um conjunto de cadeias, partindo de um conjunto de pontos escolhidos arbitrariamente e suficientemente distantes entre si. Essas cadeias são processos estocásticos de "caminhantes" que se movem aleatoriamente de acordo com um algoritmo que procura lugares com uma contribuição razoavelmente alta para a integral para onde se mover em seguida, atribuindo a eles probabilidades mais altas.

Os métodos de Monte Carlo de caminhada aleatória são um tipo de simulação aleatória ou método de Monte Carlo. Entretanto, enquanto as amostras aleatórias do integrando usadas em uma integração convencional de Monte Carlo são estatisticamente independentes, aquelas usadas em MCMC são autocorrelacionadas. Correlações de amostras introduzem a necessidade de usar o teorema do limite central da cadeia de Markov ao estimar o erro de valores médios.

Esses algoritmos criam cadeias de Markov de modo que tenham uma distribuição de equilíbrio que é proporcional à função dada.

História O desenvolvimento dos métodos MCMC está profundamente enraizado na exploração inicial das técnicas de Monte Carlo (MC) em meados do século XX, particularmente na física. Esses desenvolvimentos foram marcados pelo algoritmo de Metropolis, proposto por Nicholas Metropolis, Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller e Edward Teller em 1953, que foi projetado para lidar com problemas de integração de alta dimensão usando os primeiros computadores. Em 1970, W. K. Hastings generalizou esse algoritmo e, inadvertidamente, introduziu a ideia de atualização componente a componente, posteriormente conhecida como amostragem de Gibbs. Simultaneamente, os fundamentos teóricos para a amostragem de Gibbs estavam sendo desenvolvidos, como o teorema de Hammersley-Clifford, do artigo de Julian Besag de 1974. Embora as sementes do MCMC tenham sido plantadas anteriormente, incluindo a nomeação formal da amostragem de Gibbs no processamento de imagens por Stuart Geman e Donald Geman (1984) e o método de aumento de dados por Martin A. Tanner e Wing Hung Wong (1987), sua "revolução" na estatística convencional seguiu-se em grande parte às demonstrações da universalidade e facilidade de implementação de métodos de amostragem (especialmente a amostragem de Gibbs) para problemas estatísticos complexos (particularmente bayesianos), impulsionadas pelo aumento do poder computacional e por softwares como o BUGS. Essa transformação foi acompanhada por avanços teóricos significativos, como o tratamento rigoroso da convergência do MCMC por Luke Tierney (1994) e a análise da estrutura do amostrador de Gibbs por Jun S. Liu, Wong e Augustine Kong (1994, 1995). Desenvolvimentos subsequentes expandiram ainda mais o conjunto de ferramentas MCMC, incluindo filtros de partículas (Monte Carlo Sequencial) para problemas sequenciais, amostragem perfeita visando simulação exata (Jim Propp e David B. Wilson, 1996), RJMCMC (Peter J. Green, 1995) para lidar com modelos de dimensão variável e investigações mais profundas sobre diagnósticos de convergência e o Teorema Central do Limite. No geral, a evolução do MCMC representa uma mudança de paradigma na computação estatística, permitindo a análise de inúmeros modelos complexos anteriormente intratáveis e expandindo continuamente o escopo e o impacto da estatística.

Contexto matemático Suponha que (Xn) seja uma cadeia de Markov no espaço de estado geral com propriedades específicas. Estamos interessados no comportamento limite das somas parciais:

quando n tende ao infinito. Em particular, esperamos estabelecer a Lei dos Grandes Números e o Teorema Central do Limite para MCMC. A seguir, apresentamos algumas definições e teoremas necessários para os importantes resultados de convergência. Em resumo, precisamos da existência de uma medida invariante e recorrência de Harris para estabelecer a Lei dos Grandes Números para o MCMC (Teorema Ergódico). E precisamos de aperiodicidade, irredutibilidade e condições extras, como reversibilidade, para garantir que o Teorema Central do Limite seja válido em MCMC.Robert and Casella (2004), pp. 205–246

Irredutibilidade e aperiodicidade Lembre-se de que, no contexto discreto, uma cadeia de Markov é dita irredutível se for possível alcançar qualquer estado a partir de qualquer outro estado em um número finito de passos com probabilidade positiva. No entanto, no contexto contínuo, as transições ponto a ponto têm probabilidade zero. Nesse caso, φ-irredutibilidade generaliza a irredutibilidade usando uma medida de referência φ no espaço mensurável .

Definição (φ-irredutibilidade)

Dada uma medida definida em , a cadeia de Markov com kernel de transição é φ-irredutível se, para todo com , existe de modo que para todos (Equivalentemente, , aqui é o primeiro para a qual a cadeia entra no conjunto ).

Esta é uma definição mais geral para a irredutibilidade de uma cadeia de Markov em um espaço de estados não discreto. No caso discreto, uma cadeia de Markov irredutível é dita aperiódica se tiver período 1. Formalmente, o período de um estado é definido como:

Para o caso geral (não discreto), definimos a aperiodicidade em termos de conjuntos pequenos:

Definição (duração do ciclo e conjuntos pequenos)

Uma cadeia de Markov φ-irredutível possui um ciclo de comprimento d se existir um pequeno conjunto , um número inteiro associado e uma distribuição de probabilidade tal que d seja o máximo divisor comum de:

Um conjunto é chamado de pequeno se existir e uma medida diferente de zero de modo que:

Recorrente de Harris

Definição (recorrência de Harris)

Um conjunto é recorrente de Harris se para todo , onde é o número de visitas da cadeia ao conjunto .

A cadeia diz-se que é recorrente de Harris se existir uma medida de modo que a cadeia seja -irredutível e todo conjunto mensurável com seja recorrente de Harris.

Um critério útil para verificar a recorrência de Harris é o seguinte:

Proposição

Se para cada , nós temos para cada , então para todos e a cadeia é recorrente de Harris.

Essa definição só é necessária quando o espaço de estados é não enumerável. No caso enumerável, a recorrência corresponde a , que é equivalente a para todo .

Definição (medida invariante)

Uma -medida finita é dita invariante para o kernel de transição (e a cadeia associada) se:

Quando existe uma medida de probabilidade invariante para uma cadeia ψ-irredutível (e, portanto, recorrente), diz-se que a cadeia é recorrente positiva. Cadeias recorrentes que não admitem uma medida invariante finita são chamadas de recorrentes nulas.

Em aplicações de Cadeias de Markov Monte Carlo (MCMC), um critério muito útil para a recorrência de Harris envolve o uso de funções harmônicas limitadas.

Definição (função harmônica)

Uma função mensurável é dita harmônica para a cadeia se:

Essas funções são invariantes em relação ao kernel de transição no sentido funcional e ajudam a caracterizar a recorrência de Harris.

Proposição

Para uma cadeia de Markov positiva, se as únicas funções harmônicas limitadas forem as funções constantes, então a cadeia é recorrente de Harris.

Lei dos Grandes Números para MCMC

Teorema (Teorema Ergódico para MCMC)

Se tem uma -medida invariante finita , então as duas afirmações seguintes são equivalentes:

A cadeia de Markov é recorrente de Harris. Se com , então

Este teorema fornece uma justificativa fundamental para o uso de métodos de Monte Carlo via Cadeias de Markov (MCMC) e serve como contrapartida da Lei dos Grandes Números (LGN) no método clássico de Monte Carlo.

Um aspecto importante desse resultado é que não precisa ser uma medida de probabilidade. Portanto, pode haver algum tipo de estabilidade forte mesmo que a cadeia seja recorrente nula. Além disso, a cadeia de Markov pode ser iniciada a partir de um estado arbitrário.

Se é uma medida de probabilidade, podemos fazer e obter

Este é o Teorema Ergódico com o qual estamos mais familiarizados.

Teorema Central do Limite para MCMC Existem diversas condições sob as quais o Teorema Central do Limite (TLC) é válido para métodos de Monte Carlo via Cadeias de Markov (MCMC). Uma das mais comumente utilizadas é a condição de reversibilidade.

Definição (Reversibilidade)

Uma cadeia de Markov estacionária é dita reversível se a distribuição de dado é a mesma que a distribuição de dado .

Isso é equivalente à condição de balanço detalhado, que é definida da seguinte forma:

Definição (Balanço detalhado)

Uma cadeia de Markov com núcleo de transição satisfaz a condição de balanço detalhado se existir uma função tal que:

para cada par no espaço de estados.

Teorema (Teorema Central do Limite sob reversibilidade)

Se é aperiódica, irredutível e reversível, com distribuição invariante , então:

onde

e

.

Embora a reversibilidade seja uma suposição restritiva em teoria, ela é frequentemente satisfeita com facilidade em algoritmos MCMC práticos, introduzindo variáveis auxiliares ou utilizando mecanismos de proposta simétricos. Existem muitas outras condições que podem ser usadas para estabelecer o Teorema Central do Limite para MCMC, como a ergodicidade geométrica e o espaço de estados discreto.

Autocorrelação Os métodos MCMC produzem amostras autocorrelacionadas, ao contrário das técnicas padrão de Monte Carlo, que extraem amostras independentes. A autocorrelação significa que as extrações sucessivas da cadeia de Markov são estatisticamente dependentes, de modo que cada nova amostra adiciona menos informação nova do que uma extração independente. Consequentemente, é necessário levar em conta essa correlação ao avaliar a precisão das estimativas da cadeia. Em particular, a autocorrelação positiva na cadeia aumenta a variância dos estimadores e retarda a convergência das médias amostrais em direção ao valor esperado.

Autocorrelação e eficiência O efeito da correlação na estimação pode ser quantificado através do Teorema central do limite da cadeia de Markov. Para uma cadeia que visa uma distribuição com variância , a variância da média da amostral após passos é aproximadamente , onde é um tamanho de amostra efetivo menor que . De forma equivalente, isso pode ser expresso como:

onde é a média amostral e é a autocorrelação da cadeia na defasagem , definida como . O termo entre parênteses, , é frequentemente chamado de autocorrelação integrada. Quando a cadeia não possui autocorrelação ( para todos ), este fator é igual a 1, e recupera-se a variância usual de para amostras independentes. Se as amostras da cadeia forem altamente correlacionadas, a soma das autocorrelações será grande, levando a uma variância muito maior para do que no caso independente.

Tamanho efetivo da amostra (ESS)