1762 Simulação de Sistemas
6
Elvio
Método de Monte Carlo
Definição: Qualquer método que resolva um problema através da geração
apropriada de números aleatórios e da observação da fração destes números
que seguem uma determinada propriedade.
O método é útil para obter soluções numéricas para problemas cuja solução
analı́tica é muito complexa. O método foi formalizado em um artido de de
Nicolas Metropolis e S. Ulam publicado em 1949. Aparentemente, o nome
foi cunhado por Ulam em 1946 em honra de um parente viciado em jogos.
Agulha de Buffon. Proposto pelo Conde de Buffon há mais de 200 anos,
o problema consiste no seguinte. Se uma agulha de comprimento l é solta
aleatóriamente no meio de uma superfı́cie horizontal marcada com linhas
paralelas e separadas por uma distância d (sendo d > l), qual é a probabilidade da agulha cruzar uma das linhas?
Figura 1: Agulha de Buffon.
A posição da agulha em relação às linhas próximas pode ser descrito pela
variável aleatória a ∈ [0, d) e θ ∈ [0, π). A variável aleatória (a, θ) é uniformemente distribuida no plano [0, d) × [0.π), isto é, tem valor 1/dπ nessa
região e 0 fora dela. Portanto, a probabilidade P da agulha cruzar uma das
linhas é dada por
Z π Z l sin(θ)
1
2l
da dθ =
P =
dπ
dπ
0
0
A partir desses resultados é possı́vel elaborar um método para estimar o valor
da constante π (embora sem grande eficiência). Executando o experimento
de Buffon N vezes, seja M o número de vezes que a agulha cruza uma linha.
A probabilidade da agulha cruzar uma das linhas pode então ser estimada
como
M
.
P̂ =
N
UEM/DIN
1
1762 Simulação de Sistemas
Elvio
Se N é suficientemente grande, temos que
P̂ ≈
2l
dπ
π≈
2l
.
dP̂
e portanto
A Tab. 1 apresenta resultados obtidos em 1864. Percebe-se que com a superfı́cie rodando, o valor de π estimado está mais próximo do valor exato.
N
M
l
500 236 3 pol
530 253 3 pol
d
4 pol
4 pol
superfı́cie
estacionária
rotante
estimativa π
3,1780
3,1423
Tabela 1: Resultados do experimento de Buffon.
Existe uma outra maneira de olhar esse experimento: o valor de P̂ obtido é
também uma estimativa da integral
P̂ ≈
Z π Z l sin(θ)
1
0
0
dπ
da dθ
De modo genérico, temos que
Ψ=
Z 1Z 1
0
0
...
Z 1
0
f (u1 , u2 , . . . , uN ) du1 du2 . . . duN
onde f (u1 , u2 , . . . , uN ) é uma função multidimensional definida no espaço
(0, 1)N . Desde que a integral de interesse possa ser convertida para a forma
acima (o que em geral é possı́vel com mudanças apropriadas de variáveis),
pode-se utilizar o método de Monte Carlo para estimar a resultado da integração.
Considere u = (u1 , u2 , . . . , uN ) uma variável aleatória de dimensão N , uniformemente distribuida na região de integração (0, 1)N . Aplicando-se a função
f (.) a u e calculando a média, temos
Z
E{f (u)} =
(0,1)N
f (u) φ(u) du
onde φ(u) é a PDF de u. Como ui é uniformente distribuida no intervalo
(0, 1), temos que φ(u) = 1 e portanto
Z
E{f (u)} =
UEM/DIN
(0,1)N
f (u) du = Ψ.
2
1762 Simulação de Sistemas
Elvio
Portanto, o valor da integral pode ser estimada como a média estatı́stica de
f (u). Esta é a sı́ntese do Método de Monte Carlo.
Exemplo. Estime a área de um cı́rculo utilizando o Método de Monte Carlo.
Suponha um cı́rculo de diâmetro unitário, circunscrito a um quadrado de lado
unitário. Define-se uma variável aleatória bidimensional u = (u1 , u2 ), sendo
u1 , u2 uniformemente distribuı́das no intervalo (0, 1). Um número N (grande)
de amostras de u são obtidas. Algumas destas amostras, digamos NC , cai
dentro do cı́rculo. O restante, N − NC , cai entre o cı́rculo e o quadrado
(evidentemente todas as amostras estão dentro do quadrado). Portanto
Área Cı́rculo = Área Quadrado ×
UEM/DIN
NC
.
N
3