Métodos de Monte Carlo

Em 1946, enquanto se recuperava de uma encefalite, o matemático Stanislaw Ulam [1] jogava paciência. Ele tentou calcular as probabilidades no jogo usando análise combinatória, mas depois de gastar bastante tempo fazendo cálculos, percebeu que uma alternativa mais prática seria simplesmente realizar inúmeras jogadas (por exemplo, cem, ou mil) e contar quantas vezes cada resultado ocorria [2].

Figura 1: Stanislaw Ulam, Richard Feynman e John von Neumann ¹.

Sendo matemático, Ulam sabia que técnicas de amostragem estatística não estavam sendo muito usadas por envolverem cálculos extremamente demorados, tediosos e sujeitos a erros. Entretanto nessa época ficara pronto o primeiro computador eletrônico, desenvolvido durante a segunda guerra mundial, o ENIAC; antes dele usavam-se dispositivos mecânicos para fazer cálculos. A versatilidade e rapidez do ENIAC, sem precedentes para a época, impressionaram Ulam, que sugeriu o uso de métodos de amostragem estatística para solucionar o problema da difusão de nêutrons em material sujeito a fissão nuclear. Nicholas Metropolis sugeriu o nome Monte Carlo para o método estatístico, inspirado em um tio de Ulam que sempre pegava dinheiro emprestado com parentes para ir até Monte Carlo jogar [3].

Figura 2: Le Casino de Monte-Carlo, em Mônaco .

Métodos de Monte Carlo são métodos que usam amostragens estatísticas para resolver de maneira aproximada problemas complexos, realizando grande quantidade de experimentos; estes experimentos não são realizados de verdade, mas apenas teoricamente. Sendo cada experimento composto por várias etapas, e conhecendo a probabilidade de cada resultado ocorrer em cada uma dessas etapas, pode-se conhecer os resultados finais após as diversas etapas que compõe um experimento, após inúmeros experimentos. Para simular a aleatoriedade nesses experimentos usa-se listas de números aleatórios [4].

Se o experimento em estudo fosse a soma dos números obtidos com a rolagem de dois dados, o experimento consistiria em duas etapas: a rolagem do primeiro dado, e a rolagem do segundo dado. Em cada etapa, a probabilidade de cada número ocorrer (de 1 a 6) seria 1/6, supondo que os dados não estivessem viciados. Usando uma lista de números aleatórios que variassem de 1 a 6, um método de Monte Carlo simularia inúmeras jogadas de 2 dados, e contaria quantas vezes ocorreu o valor 2 (dado pela soma do primeiro dado com número 1, mais o segundo dado, também com 1), quantas vezes ocorreu o valor 3 (primeiro dado com 1 e o segundo com 2, ou o primeiro com 2 e o segundo com 1), e assim por diante, até o valor 12 (ambos os dados com 6). Esse problema é suficientemente simples para ser resolvido por análise combinatória, mas serve aqui para exemplificar o método.

Uma utilização frequente dos métodos de Monte Carlo é na integração numérica. Na figura abaixo, a integral da função é a área entre a função, o eixo dos x, o eixo f(x), e uma linha paralela ao eixo f(x) onde x=5. Enquanto outros métodos de integração numérica utilizam aproximações polinomiais, a integração por Monte Carlo escolhe aleatoriamente pontos no intervalo em que se deseja obter a integral, neste caso de x=0 a x=5; nesses pontos os valores da função são calculados, e assim se obtém o valor médio da função no intervalo. Então basta multiplicar o valor médio obtido pelo intervalo; neste caso este valor é 5, que é a diferença entre o valor final em x (5) e o valor inicial em x (0). É como se estivéssemos calculando a área de um retângulo. Na figura vemos quinze pontos escolhidos, mas na prática usa-se uma quantidade bem maior de pontos aleatórios, o que entretanto não impede que estes cálculos sejam feitos rapidamente por um computador.

Figura 3: a linha azul é uma função em x. Em vermelho estão pontos escolhidos aleatoriamente para calcular o valor médio da função.

Métodos de Monte Carlo são utilizados em integração quando outras técnicas são muito difíceis ou impossíveis de serem utilizadas. Outra situação em que métodos MC são mais eficientes é quando temos muitas dimensões no integrando, já que a incerteza ao integrar com Monte Carlo não muda com o acréscimo de mais dimensões [5].
A abordagem estatística que Stan Ulam sugeriu a John Neumann permitiu a estimativa da taxa de multiplicação de nêutrons nas armas nucleares que estavam sendo desenvolvidas na época. Hoje métodos de Monte Carlo são utilizados como ferramenta no auxílio à pesquisa nos mais variados campos, entre os quais podemos citar desenho de reator nuclear [6], cromodinâmica quântica [7], terapia de câncer por radiação [8], fluxo de tráfego [9], evolução estelar [10], sistemas de muitos corpos interagentes [11] e econometria [12].

[1] "Stanislaw Marcin Ulam." Encyclopædia Britannica. 2008. Encyclopædia Britannica Online. 04 May. 2008
[2] Stam Ulam, John Von Neumann, and the Monte Carlo method, Los Alamos Science n. 15, pg 131 (1987).
[3] The beginning of the Monte Carlo method, N. Metropolis, Los Alamos Science n. 15, pg 125 (1987).
[4] The Monte Carlo method, N. Metropolis, S. Ulam, Journal of American Statistical Association, vol 44 n. 247 pg 335 (1949)
[5] A first course in computational physics, Paul L. DeVries, John Wiley & Sons (1994)
[6] Monte Carlo transport calculations and analysis for reactor pressure vessel neutron fluence, J C Wagner, A Haghighat, B G Petrovic, Nuclear Technology, 114:373 (1996)
[7] Quantum Monte Carlo calculations of six-quark states, M W Paris, V R Pandharipande, Physical Review C, 62:015201 (2000)
[8] Summary and recommendations of a National Cancer Institute workshop of Monte Carlo dose calculation algorithms for megavoltage external beam radiation therapy, B A Fraass, J Smathers, J Deye, Medical Physics, 30:3206 (2003)
[9] A stochastic multi-cluster mode of freeway traffic, J Kaupuzs, R Mahnkel, European Physical Journal B, 14:793 (2000)
[10] Monte Carlo simulations of star clusters - I. First results, Mirek Giersz, Monthly Notices of the Royal Astronomical Society, 298:1239 (1998)
[11] Monte Carlo Methods in Statistical Physics, K. Binder, Springer-Verlag (1979)
[12] Option pricing when the variance changes randomly: theory, estimation and an application, Louis O. Scott, The Journal of Financial and Quantitative Analysis, 22:419 (1987)