Método de Monte
Carlo
RAPHAEL OLIVEIRA LOURENÇO
EVOLUÇÃO DA CIÊNCIA E DA MATEMÁTICA
Introdução

Métodos de Monte Carlo são uma classe ampla de algoritmos
computacionais que dependem de amostragens para obtenção
de resultados numéricos. O nome vem da semelhança da técnica
para o ato de observar e gravar os resultados em um cassino real.

O método é muito utilizado em problemas físicos e matemáticos e
é mais útil quando é difícil ou impossível obter uma expressão em
forma fechada, ou impraticáveis para aplicar um algoritmo
determinista.

Métodos de Monte Carlo são usados principalmente em três
classes distintas: problemas de otimização, integração numérica e
geração de sorteios a partir de uma distribuição de probabilidade.
Introdução

Em problemas relacionados com a física, métodos de Monte Carlo
são bastante úteis para sistemas de simulação com muitos graus de
liberdade acoplados, como fluidos, materiais desordenados, sólidos
fortemente acoplados, e estruturas celulares.

Outros exemplos incluem fenômenos de modelagem com
incerteza significativa em insumos, como o cálculo de risco em
finanças e, em matemática, avaliação de integrais definidas
multidimensionais com condições de contorno complicados.

Em aplicação a problemas de exploração de petróleo, Métodos
baseados em Monte Carlo para previsões de fracasso, excesso de
custos e atrasos no cronograma são rotineiramente melhor do que
a intuição humana.
Introdução

Antes de o método de Monte Carlo ser desenvolvido, simulações
testavam um problema determinístico anteriormente entendido e
uma amostragem estatística era utilizado para estimar incertezas
nas simulações.

Simulações de Monte Carlo vem com o objetivo de inverter esta
abordagem, resolvendo problemas determinísticos usando um
análogo probabilístico.
Origem e História

Uma variante de início do método de Monte Carlo pode ser visto
na experiência agulha de Buffon, em que π pode ser estimada por
queda agulhas em um piso feito de faixas paralelas e equidistantes.
Na década de 1930, Enrico Fermi fez a primeira experiência com o
método de Monte Carlo, de fato, enquanto estudava difusão de
nêutrons, mas não publicou nada sobre ele.
Origem e História

Em 1946, os físicos no Laboratório Científico de Los Alamos estavam
investigando proteção contra radiações e da distância que os
nêutrons provavelmente iriam viajar através de vários materiais.

Apesar de ter a maior parte dos dados necessários, tais como a
distância média que um nêutron iria viajar em uma substância
antes de colidir com um núcleo atômico, e quanta energia o
nêutron era susceptível a emitir após uma colisão, os físicos de Los
Alamos foram incapazes de resolver o problema usando métodos
matemáticos convencionais, deterministas. Stanislaw Ulam teve a
idéia de usar experimentos aleatórios.
Origem e História

Em 1946, os físicos no Laboratório Científico de Los Alamos estavam
investigando proteção contra radiações e da distância que os
nêutrons provavelmente iriam viajar através de vários materiais.

Apesar de ter a maior parte dos dados necessários, tais como a
distância média que um nêutron iria viajar em uma substância
antes de colidir com um núcleo atômico, e quanta energia o
nêutron era susceptível a emitir após uma colisão, os físicos de Los
Alamos foram incapazes de resolver o problema usando métodos
matemáticos convencionais, deterministas. Stanislaw Ulam teve a
idéia de usar experimentos aleatórios.
Origem e História

Stanisław Marcin Ulam foi um matemático polonêsamericano de renome. Ele participou do Projeto
Manhattan da América, originou o projeto Teller-Ulam das
armas termonucleares, inventou o método de Monte
Carlo de computação, e sugeriu a propulsão de pulso
nuclear. Em matemática pura e aplicada, ele produziu
muitos resultados, mostrou muitos teoremas, e propôs
várias conjecturas.
Origem e História

Ulam compartilhou sua ideia com outro brilhante Matemático:
John von Neumann (a nível de curiosidade, o artigo sobre ele na
wikipedia cita ao menos 25 áreas diferentes da ciência em que
von Neumann fez contribuições importantes).

Por trabalharem em secreto no desenvolvimento do método, eles
precisavam de um “codinome”. Ulam e von Neumann
escolheram Monte Carlo, que se refere ao Casino Monte Carlo,
em Mônaco, onde o tio de Ulam sempre ia jogar, chegando a
pedir dinheiro emprestado para tal.
Definição Simples

Métodos de Monte Carlo variam, mas tendem a seguir
um determinado padrão:
 Definir
um domínio de possíveis entradas.
 Gerar
entradas aleatoriamente a partir de uma distribuição
de probabilidade sobre o domínio.
 Agregar
os resultados.
Monte Carlo e os números Aleatórios

Métodos de simulação de Monte Carlo nem sempre exigem
números verdadeiramente aleatórios para serem uteis. Enquanto
que para algumas aplicações, tais como testes de primalidade, a
imprevisibilidade é vital. Muitas das técnicas mais úteis usam,
sequências pseudo-deterministas (ou pseudorrandômicas),
tornando mais fácil para testar e reexecutar simulações. A única
qualidade que normalmente é necessário para fazer boas
simulações é a sequência pseudoaleatória parecer “aleatória o
suficiente" em certo sentido.
Monte Carlo e os números Aleatórios

Esse sentido irá variar para cada aplicação, mas normalmente eles
devem passar por uma série de testes estatísticos. Testando que os
números são uniformemente distribuídas ou seguir outro distribuição
desejada quando um grande número suficiente de elementos da
seqüência são considerados é um dos mais simples e mais comuns.
Fraca correlação entre amostras sucessivas é também muitas vezes
desejável / necessário.
Monte Carlo e os números Aleatórios

Sawilowsky lista as características de uma alta qualidade de
simulação de Monte Carlo.

O gerador de números (pseudo-aleatório) tem determinadas
características (por exemplo, uma longa "período" antes da
repetição da sequência)

o gerador de números (pseudo-aleatório) produz valores que
passam nos testes de aleatoriedade

existem amostras suficientes para garantir resultados precisos

a técnica de amostragem apropriada é utilizada
Aplicação 1: Integração de Monte
Carlo

Algoritmos determinísticos de integração numérica funcionam bem
em um pequeno número de dimensões, mas encontramos dois
problemas quando as funções têm muitas variáveis. Em primeiro
lugar, o número de cálculos das funções necessárias aumenta
rapidamente com o número de dimensões. Por exemplo, se 10
avaliações fornecer uma precisão adequada em uma dimensão,
são necessários, em seguida, 10100 pontos para 100 dimensões. Isso
é chamado de maldição da dimensionalidade.

Em segundo lugar, o limite de uma região multidimensional pode
ser muito complicado, de modo que pode não ser viável para
reduzir o problema de uma série de integrais unidimensionais
encaixadas.
Aplicação 1: Integração de Monte
Carlo

Métodos de Monte Carlo fornecem uma maneira de sair deste
aumento exponencial do tempo de computação. Enquanto a
função em questão está razoavelmente bem comportado, pode
ser estimada por pontos selecionados aleatoriamente no espaço
100-dimensional, e tendo algum tipo de média dos valores da
função nestes pontos. Pelo teorema do limite central, este método
mostra convergência da ordem de 𝑁, ou seja, quadruplicando o
número de pontos amostrados reduz pela metade o erro,
independentemente do número de dimensões.
Aplicação 1: Integração de Monte
Carlo
Aplicação 2: Estimando 𝜋

Por exemplo, considere um quarto de círculo inscrito em um
quadrado unitário. Dado que o quarto de círculo e o quadrado
tem uma relação de áreas que é 𝜋 / 4, o valor de 𝜋 pode ser
aproximado através de Monte Carlo:

Desenhe um quadrado no chão, em seguida, inscreva um quarto
de círculo dentro dele.

Uniformemente disperse alguns objetos de tamanho uniforme
(grãos de arroz ou areia) sobre o quadrado.

Contar o número de objetos no interior do círculo e o número total
de objetos.

A razão das duas contagens é uma estimativa da proporção das
duas áreas, que é 𝜋 / 4. Multiplique o resultado por 4 a estimar 𝜋.
Aplicação 2: Estimando 𝜋

Neste procedimento, o domínio de insumos é a praça que
circunscreve nosso círculo. Geramos entradas aleatórias por
espalhamento de grãos sobre a praça, em seguida, fazemos um
cálculo em cada entrada (teste se ele cai dentro do círculo).
Finalmente, agregar os resultados para obter o nosso resultado final,
a aproximação de 𝜋.
Aplicação 2: Estimando 𝜋
Bibliografia

http://en.wikipedia.org/wiki/Monte_Carlo_method

http://en.wikipedia.org/wiki/Stanislaw_Ulam

http://en.wikipedia.org/wiki/Buffon%27s_needle

Christian Robert & George Casella - Monte Carlo Statistical Methods