Método de Monte Carlo

Da Thinkfn
Revisão das 14h24min de 13 de novembro de 2008 por Incognitus (discussão | contribs)

(dif) ← Revisão anterior | Revisão atual (dif) | Revisão seguinte → (dif)

Aplicação do método de Monte Carlo para determinar a área de um lago.

O método de Monte Carlo (MMC) é um método estatístico utilizado em simulações estocásticas com diversas aplicações em áreas como a física, matemática e biologia. O método de Monte Carlo tem sido utilizado há bastante tempo como forma de obter aproximações numéricas de funções complexas. Este método tipicamente envolve a geração de observações de alguma distribuição de probabilidades e o uso da amostra obtida para aproximar a função de interesse. As aplicações mais comuns são em computação numérica para avaliar integrais. A idéia do método é escrever a integral que se deseja calcular como um valor esperado.

De acordo com (HAMMERSELEY,1964) o nome "Monte Carlo" surgiu durante o projeto Manhattan na Segunda Guerra Mundial. No projeto de construção da bomba atómica, Ulam, von Neumann e Fermi consideraram a possibilidade de utilizar o método, que envolvia a simulação directa de problemas de natureza probabilistica relacionados com o coeficiente de difusão do neutrão em certos materiais. Apesar de ter despertado a atenção desses cientistas em 1948, a lógica do método já era conhecida há bastante tempo. Por exemplo, existe um registo de um artigo escrito por Lord Kelvin dezenas de anos antes que já utilizava técnicas de Monte Carlo numa discussão das equações de Boltzmann.

Classes

Existem três classes de algoritmos Monte Carlo: Erro-Unilateral, Erro-Bilateral e Erro-Não-Limitado.

Monte Carlo de Erro-Unilateral

Seja P um problema e A um algoritmo aleatório, A é um algoritmo Monte Carlo de Erro-Unilateral que resolve P se

  1. para toda configuração x que é solução de P, prob(A(x = SIM )) \geq \frac{1}{2}, e
  2. para toda configuração x que não é solução de P, prob(A(x) = NÃO ) = 1

Ou seja, sempre que a resposta é NÃO, o algoritmo garante a certeza da resposta. Contudo, se a resposta for SIM, o algoritmo não garante que a resposta está correta..

Monte Carlo de Erro-Bilateral

Um algoritmo aleatório A é um algoritmo de Monte Carlo de Erro-Bilateral que computa o problema F se existe um número real \epsilon, tal que para toda instância x de F

prob(A(x) = F(x)) \geq \frac{1}{2} + \epsilon

Monte Carlo de Erro-Não-Limitado

Os algoritmos Monte Carlo de Erro-Não-Limitado são comumente chamados de Algoritmos Monte Carlo.

Um algoritmo aleatório A é um algoritmo de Monte Carlo se para qualquer entrada x do problema F

prob(A(x) = F(x)) > \frac{1}{2}


Algoritmo de Metropolis

Fluxograma para o algoritmo de Metropolis. Fonte: Wikimedia, criador: Leonardo Castro. O algoritmo de Metropolis, também conhecido por Algoritmo de Metropolis-Hastings, desenvolvido por Nicholas Metropolis e W. K. Hastings, é provavelmente o método Monte Carlo mais utilizado na Física, e tem como objetivo determinar valores esperados de propriedades do sistema simulado, através de uma média sobre uma amostra. O algoritmo é concebido de modo a obter-se uma amostra que siga a distribuição de Boltzmann.

Para se determinar a probabilidade de uma dada configuração, seria necessário conhecer a probabilidade de ocorrência de todas as outras configurações. No caso de variáveis contínuas, seria necessário uma integração da densidade de probabilidade sobre todo o espaço de configurações, mas esse procedimento é muito dispendioso quando se utiliza um número de variáveis da ordem de centenas.

A eficiência do algoritmo de Metropolis está diretamente ligada ao facto de não levar em conta a probabilidade das configurações em si, mas sim a razão entre elas, pois a razão entre as probabilidades de duas dadas configurações pode ser determinada independentemente das outras. Dadas duas configurações m e n quaisquer, a razão entre a probabilidade da configuração m, P_m, e a probabilidade da configuração n, P_n, pode ser escrita como

\frac{P_m}{P_n} = \frac{exp(-\frac{U_m}{k_bT})}{exp(-\frac{U_n}{k_bT}) } = exp(-\frac{U_m-U_n}{k_bT})

A partir dessa igualdade, o algoritmo de Metropolis pode ser implementado através do seguinte conjunto de regras:

(a) Geração de uma configuração inicial aleatória, ou seja, com valores aleatórios para todos os graus de liberdade do sistema, respeitando as suas restrições. Vamos atribuir o índice m a essa configuração, que é aceite para a amostra.
(b) Geração de uma nova configuração-tentativa de índice n, resultado de pequenas alterações nas coordenadas da configuração m.
(c) Se a energia da configuração n for menor que a da configuração m, inclui-se a configuração n na nossa amostra e atribui-se-lhe o índice m a partir desse momento. Caso contrário, realizam-se os passos descritos nos subitems (c1) e (c2) abaixo:
(c1) Gera-se um número aleatório entre 0 e 1;
(c2) Se esse número aleatório for menor que \frac{P_n}{P_m}, aceita-se na amostra a configuração n, e atribui-se-lhe o índice m. Caso contrário, o índice m continua designando a configuração original.
(d) Repete-se os passos (b) e (c) até que algum critério de paragem seja satisfeito. Cada uma dessas repetições é dita um passo em Monte Carlo (MC).

Referências

  • ((en)) HROMKOVIC, J. Algorithms for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics. [S.l.]: Springer-Verlag London Berlin Heidelberg New York, 2001.



Smallwikipedialogo.png

Esta página usa conteúdo da Wikipedia. O artigo original estava em Método de Monte Carlo. Tal como o Think Finance neste artigo, o texto da Wikipedia está disponível segundo a GNU Free Documentation License.