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

 

i) para toda configuração x que é solução de P,                                    , e

 

ii) para toda configuração x que não é solução de P,                                     

 

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 positivo       , tal que para toda instância x de F

 

 

 

 

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.

 

 

 

 

 

 

Algoritmo de Metropolis:

 

O algoritmo de Metropolis, também conhecido por Algoritmo de Metropolis-Hastings, apresentado inicialmente em 1953 num artigo de Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller e Edward Teller, e generalizado em 1970 por 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 se obter uma Amostra que siga a Distribuição de Boltzmann.

 

 

Para se determinar a probabilidade de uma dada configuração, seria necessário conhecer a chance 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 tem signicativo custo quando se utiliza um número de variáveis da ordem de centenas.

 

 

A eficiência do algoritmo de Metropolis está diretamente ligada ao fato 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, Pm] e a probabilidade da configuração [n, Pn] pode ser escrita como

 

 

 

 

 

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 é aceita 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 se atribui a ela 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 Pn/Pm, aceita-se na amostra a configuração n, e se atribui a ela o índice m. Caso contrário, o índice m permanece designando a configuração original.

 

(d) Repete-se os passos (b) e (c) até que algum critério de parada seja satisfeito. Cada uma dessas repetições é dita um passo Monte Carlo (MC).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fluxograma para o Algoritmo de Metropolis. Fonte: Wikimedia, criador: Leonardo Castro.

 

 

 

 

 

 

Referências

1. Hromkovic, J. "Algorithms for hard problems": introduction to combinatorial optimization, randomization, approximation, and heuristics. [S.l.]: Springer-Verlag, London - Berlin - Heidelberg - New York, 2001.

2. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. "Equation of State Calculations by Fast Computing Machines", Journal of Chemical Physics 21, 1087 (1953).

3. Hastings, W. K. "Monte Carlo Sampling Methods Using Markov Chains and Their Applications", Biometrika 57 (1), 97 (1970).