Ler o artigo completo

Números (Pseudo) Aleatórios, Probabilidade
Geométrica, Métodos de Monte Carlo e
Estereologia
Humberto José Bortolossi
Instituto de Matemática e Estatı́stica
Universidade Federal Fluminense
1
Números (pseudo) aleatórios
Muitos jogos de computador realizam ações que, em princı́pio, parecem ser aleatórias: embaralhar
as cartas no jogo paciência, distribuir as minas no jogo campo minado, lançar dados em um jogo de RPG
(Role Playing Game), etc. Todas estas ações são programadas a partir da suposta capacidade do computador de gerar números aleatórios. Contudo, a maioria dos computadores digitais domésticos atuais
não geram números aleatórios. O que estes computadores fazem é usar um algoritmo para produzir
números (denominados pseudoaleatórios) que “simulam” o comportamento de números aleatórios.
Um dos algoritmos mais simples para se gerar números pseudoaleatórios (e ainda muito usado em
vários programas computacionais) é o assim denominado gerador congruente linear (GCL), apresentado
por D. H. Lehmer em 1949: considere números inteiros m, a, c e s tais que m > 0, 0 ≤ a < m e
0 ≤ s < m. Escrevendo x0 = s, defina recursivamente, para cada inteiro n ≥ 0,
xn+1 = (a xn + c) mod m,
isto é, xn+1 é o resto da divisão de a xn + c por m. Por exemplo, se m = 10, a = 11, c = 3 e x0 = s = 3,
então a x0 + c = 36. Como o resto da divisão de 36 por 10 é 6, segue-se que x1 = 6. Sendo assim,
a x1 + c = 69. Como o resto da divisão de 69 por 10 é 9, segue-se que x2 = 9. Prosseguindo-se com
este esquema, a partir do número x0 = 3, geramos os números x1 = 6, x2 = 9, x3 = 2, x4 = 5, x5 = 8,
x6 = 1, x7 = 4, x8 = 7, x9 = 0 e x10 = 3. Note que depois de x10 , a sequência de números gerados
se repete (com perı́odo 10). As constantes m, a e c são escolhidas seguindo basicamente dois critérios:
(1) o método deve gerar um grande número de valores diferentes (isto é, o perı́odo da sequência deve
ser longo) e (2) o método deve gerar números rapidamente. Os GCLs geram números inteiros positivos
entre 0 e m. Para gerar números decimais entre 0 e 1, basta dividir os números gerados por m.
Os geradores congruentes lineares são rápidos e usam pouco memória do computador. Contudo,
dependendo da aplicação, o seu uso não é recomendável. Um defeito grave dos GCLs é que os números
gerados possuem uma correlação: triplas de números geradas aglomeram-se em um determinado número
de planos paralelos ([Marsaglia, 1968], [Knuth, 1998]). A figura a seguir ilustra este fato.
1
Nesta figura, 10000 pontos foram gerados no cubo unitário usando-se o algoritmo RANDU da IBM,
o GCL definido pela escolha m = 2147483648, a = 65539 e c = 0. O RANDU foi muito usado nos
computadores de grande porte das décadas de 1960 e 1970. Observe como os 10000 pontos gerados se
aglomeram sobre 15 planos dentro do cubo. Dado a este defeito, especialistas não recomendam o emprego de um GCL, por exemplo, em criptografia, pois um hacker poderia explorar esta particularidade
dos GCLs para descobrir os valores dos parâmetros m, a e c a partir da sequência gerada. Isto aconteceu com o antigo navegador de internet Netscape em 1995: dois alunos da Universidade de Berkeley
nos Estados Unidos conseguiram descobrir o GCL usado pelo navegador. Além dos GCLs, existem
vários outros geradores de números pseudoaleatórios: Mersenne Twister (usado no PlayStation 3 e
com perı́odo 219937 − 1), Blum Blum Shub (usado em criptografia), Xorshift de George Marsaglia, etc.
Existem geradores de números verdadeiramente aleatórios? Para responder a esta pergunta, é preciso definir antes o que se entende por um número ou evento aleatório. Esta é uma questão polêmica,
sendo ainda debatida por psicólogos, filósofos, matemáticos, fı́sicos e cientistas da computação. Por
exemplo, você poderia pensar que o lançamento de uma moeda honesta é um evento aleatório com
probabilidade “1/2” para cara e probabilidade “1/2” para coroa. Mas o lançamento de uma moeda
também pode ser pensado como um processo determinı́stico (complexo, mas ainda determinı́stico),
regido pelas leis da Fı́sica. De fato, o artigo [Diaconis, Holmes, Montgomery, 2007] descreve um experimento onde, através de um ajuste de velocidade inicial e momento angular, uma moeda lançada por
uma máquina sempre dá como resultado cara. Os excelentes artigos [Volchan, 2004] e [Volchan, 2002]
apresentam e discutem as várias definições propostas para a noção de aleatoriedade.
Mesmo sem um consenso com relação a definição de aleatoriedade, empresas têm comercializado
dispositivos que, segundo elas, produzem números verdadeiramente aleatórios. Várias técnicas são empregadas: medições de ruı́do atmosférico, medições de decaimento radioativo, fotografias de lâmpadas
de lava e processos óticos em fı́sica quântica.
A capacidade de se gerar números (pseudo) aleatórios tem várias aplicações. Por exemplo, ela é uma
peça-chave nos vários algoritmos que permitem criar simulações computacionais de diversos fenômenos
em várias ciências ([Gentle, 2003], [Ross, 2006]). Na próxima seção veremos como a geração de números
(pseudo) aleatórios pode ser usada para se calcular, de forma aproximada, medidas de comprimento,
área e volume.
2
Probabilidade Geométrica, Métodos de Monte Carlo e
Estereologia
Seguindo [Wagner, 1997], considere a situação onde um atirador, com os olhos vendados, tenta
acertar um alvo circular com 36 cm de raio tendo no centro um disco vermelho de 3 cm de raio. Se
soubermos que o atirador acertou o alvo, qual é a probabilidade de que ele tenha atingido o disco
vermelho central?
2
Note que, aqui, o espaço amostral é infinito (todos os pontos do alvo), como também é infinito o conjunto
dos casos favoráveis (todos os pontos do disco vermelho central). Mesmo não podendo “contar” casos
possı́veis e casos favoráveis, é bem razoável considerar que a probabilidade de acertar o disco central
deve ser a razão entre as áreas do disco e do alvo, no caso 1/144, menos de 0.7% (como o atirador está
vendado, não existem pontos privilegiados no alvo). Este é um exemplo de probabilidade geométrica:
se tivermos uma região B do plano contida em uma região A, admitimos que a probabilidade de
um ponto de A também pertencer a B é proporcional à área de B e não depende da posição que B
ocupa em A. Portanto, selecionado ao acaso um ponto de A, a probabilidade de que ele pertença
a B será: p = (área de B)/(área de A). Se, em vez de regiões no plano, A e B forem regiões no
espaço, então selecionado ao acaso um ponto de A, a probabilidade de que ele pertença a B será:
p = (volume de B)/(volume de A).
Usando-se a fórmula p = (área de B)/(área de A) e a geração de números (pseudo) aleatórios, podemos criar um método para estimar a área desconhecida de uma região B contida em uma região A
de área conhecida. Suponha, por exemplo, que você não saiba o valor da área do cı́rculo B de centro
(1/2, 1/2) e raio 1/2, mas saiba a área do quadrado unitário A = [0, 1] × [0, 1]. Gerando-se pares ordenados de números (pseudo) aleatórios uniformemente distribuı́dos no quadrado A, contamos o número
total m de pontos sorteados e o número n de pontos sorteados que pertencem ao cı́rculo B. O número
r = n/m dará uma aproximação de p e, portanto, o número r × (área de A) dará uma aproximação
para a área de B (no caso, π/4 = 0.78539816 . . .).
Na figura: n = 64, m = 78 e r =
n
= 0.82051282 . . . .
m
Este tipo de técnica de análise de fenômenos através de algoritmos de computador que empregam
essencialmente a geração de números (pseudo) aleatórios é denominado “Método de Monte Carlo”.
O nome “Monte Carlo” foi dado por Stanislaw Ulam (1909-1984) e John von Neumann que inventaram
o método para resolver problemas de difusão de nêutrons relacionados com projetos de armas nucleares
(Projeto Manhattan) no Laboratório Nacional de Los Alamos, Estados Unidos, por volta de 1940
([Metropolis, Ulam, 1943], [Metropolis, 1987]).
Stanislaw Ulam
John von Neumann
Segundo sua autobiografia ([Ulam, 1976]), “Stanislaw Ulam ajudou a dar forma a algumas das mudanças mais dramáticas do mundo pós-guerra. Com uma tendência experimental, que o distinguiu de
outros matemáticos, foi um dos primeiros a defender e a usar os computadores em pesquisas cientı́ficas.
3
Ulam também contribuiu com ideias para a propulsão nuclear de veı́culos espaciais e fez contribuições
fundamentais para muitos dos mais desafiadores projetos matemáticos da atualidade.”. John von Neumann é tido como um dos mais importantes matemáticos do século XX, tendo feito contribuições em
matemática, fı́sica, economia, computação e estatı́stica. Junto com Alan Turing (1912-1954) e Claude
Shannon (1916-2001), John von Neumann é considerado como um dos idealizadores do computador
digital com programas armazenados.
Um outro problema de probabilidade geométrica bem interessante foi proposto pelo naturalista
francês George-Louis Leclerc (1707-1788), Conde de Buffon: suponha que você esteja em uma sala
cujo chão é feito de ripas retangulares de madeira, todas com largura d. Ao se jogar uma agulha de
comprimento a, com a ≤ d, qual é a probabilidade da agulha ficar sobre um reta divisória de duas
ripas? Com recursos de cálculo integral, é possı́vel demonstrar (consulte, por exemplo, [Tunala, 1992])
que esta probabilidade é igual a p = (2a)/(dπ).
Estas conexões entre probabilidade e geometria formam a base da estereologia, campo interdisciplinar cujo objetivo é estudar propriedades geométricas de objetos tridimensionais usando métodos de
amostragens ([Howard, Reed, 2005], [Stroeven, Hu, 2009]): sondas geométricas (como pontos, retas,
planos e regiões volumétricas) são “jogadas” em um objeto tridimensional de interesse. A dimensão
da sonda geométrica depende do que se quer medir no objeto: para se medir o volume do objeto, as
sondas são pontos; para se medir uma área no objeto, as sondas são retas; para se medir comprimentos
no objeto, as sondas são planos; para se contar “pontos” no objeto, as sondas são regiões volumétricas.
Em cada caso, a interseção da sonda com o que se quer medir no objeto são entidades de dimensão
zero: pontos. Se as sondas são geradas aleatoriamente de forma apropriada, uma contagem destes
pontos fornecerá uma estimativa para a medida que se quer realizar. São estes métodos matemáticos
que permitem, através de um aparelho de raios-X, obter medidas de objetos no interior do corpo humano, medidas estas que são inacessı́veis de forma direta. A informação de que os pulmões humanos
têm uma superfı́cie (de troca gasosa) equivalente a um campo de tênis foi obtida usando-se métodos
estereológicos. Outras áreas que usam estereologia: petrografia (ramo da geologia que trata da descrição e classificação sistemática das rochas, especialmente através do exame microscópico de seções
delgadas), ciência dos materiais, histologia e neuroanatomia. É importante diferenciar estereologia de
tomografia computadorizada. Em tomografia computadorizada, o objeto de interesse é completamente
reconstruı́do a partir de suas seções planas e, a partir desta reconstrução, medidas podem ser feitas.
Em estereologia, o objeto não é reconstruı́do. As medidas são estimadas usando-se processos de amostragem através de sondas geométricas. Entre as tecnologias que tornam a estereologia possı́vel estão
a ressonância magnética, a ultrassonografia, a microscopia confocal de alta resolução e a microscopia
de luz convencional.
4
3
Referências
No endereço http://www.uff.br/cdme/rdf/ (ou no espelho http://www.cdme.im-uff.mat.br/rdf/)
está disponı́vel uma série de aplicativos interativos que permitem explorar a geração de números pseudoaleatórios e os métodos de Monte Carlo apresentadas neste texto. Também está disponı́vel um
arquivo DOC (o Formulário de Acompanhamento do Aluno) com várias sugestões de exercı́cios para
serem trabalhados em sala de aula. Orientações didáticas e metodológicas estão disponı́veis no Guia
do Professor.
Sugerimos as seguintes referências ao leitor interessado em mais detalhes sobre a geração de números
pseudoaleatórios, probabilidade geométrica, métodos de Monte Carlo e estereologia.
Calude, C. S. Who Is Afraid of Randomness?. CDMTCS Research Report Series, University of Auckland, New Zealand, 2000.
Diaconis, P.; Holmes, S.; Montgomery, R. Dynamical Bias in The Coin Toss. SIAM Review, vol. 49.
n. 2, pp. 211-235, 2007.
Gentle, J. E. Random Number Generation and Monte Carlo Methods. Second Edition. Statistics and
Computing, Springer-Verlag, 2003.
Howard, V.; Reed, M. G. Unbiased Stereology: Three-dimensional Measurement in Microscopy Advanced Methods. Taylor & Francis Routledge, 2005.
Knuth, D. E. The Art of Computer Programming. Volume 2. Seminumerical Algorithms. Addison
Wesley Longman, 1998.
Marsaglia, G. Random Numbers Fall Mainly in The Planes. Proceedings of the National Academy of
Sciences of the United States of America, v. 61, n. 1, pp. 25-28, 1968.
Metropolis, N. The Beginning of The Monte Carlo Method. Los Alamos Science, n. 15, pp. 125-130,
1987.
Metropolis, N.; Ulam, S. The Monte Carlo Method. Journal of The American Statistical Association,
vol. 44, n. 247, pp. 335-341, 1949.
Peterson, I. The Jungles of Randomness – A Mathematical Safari. Wiley, 1998.
Ross, S. M. Simulation. Fourth Edition. Academic Press, 2006.
Shonkwiler, R.; Mendivil, F. Explorations in Monte Carlo Methods. Undergraduate Texts in Mathematics, Springer-Verlag, 2009.
Stroeven, P.; Hu, J. Review Paper – Stereology: Historical Perspective and Applicability to Concrete
Technology. Materials and Structures, v. 39, pp. 127-135, 2006.
Tunala, N. Determinação de Probabilidades por Métodos Geométricos. Revista do Professor de Matemática, Sociedade Brasileira de Matemática, vol. 20, pp. 18-22, 1992.
Ulam, S. M. Adventures of A Mathematician. Charles Scribner’s Sons, 1976.
Volchan, S. B. What is A Random Sequence?. The American Mathematical Monthly, vol. 109, pp.
46-63, January, 2002. http://mathdl.maa.org/images/upload library/22/Ford/Volchan46-63.pdf
Volchan, S. B. A Teoria Algorı́tmica da Aleatoriedade. Em Chediak, K.; Videira, A. A. P. (Editores). Temas de Filosofia da Natureza, UERJ, pp. 123-130, 2004. http://www.uff.br/cdme/arquivos/
volchan-2002.pdf
Wagner, E. Probabilidade Geométrica – O Problema do Macarrão e Um Paradoxo Famoso. Revista do
Professor de Matemática, Sociedade Brasileira de Matemática, vol. 34, pp. 28-35, 1997.
5