Probabilidade e estatística · Método de Monte Carlo

Método de Monte Carlo

Um método de Monte Carlo estima um número por amostragem aleatória. Ao lançar N pontos uniforme e independentemente num quadrado unitário, a proporção que cai numa região estima a sua área, com erro-padrão proporcional a 1/√N. Lance pontos e observe a estimativa de π a estabilizar e a evolução da incerteza.

O método de Monte Carlo neste gráfico

Um método de Monte Carlo estima um número fixo por amostragem aleatória. Aqui trata-se de uma área: lançam-se NN pontos uniforme e aleatoriamente no quadrado unitário, HH caem numa região e H/NH/N estima a sua área aa. O quarto de círculo tem área π/4\pi/4, pelo que 4H/N4H/N estima π\pi. A região sob y=e−x2y = e^{-x^2} transforma um integral sem primitiva elementar no mesmo tipo de contagem. O gráfico inferior acompanha a estimativa à medida que NN cresce até um milhão, com o intervalo no qual se espera que caia em 95% das repetições.

Por que estima a proporção a área?

Um ponto distribuído uniformemente num quadrado de área 1 cai numa região com probabilidade igual à sua área. Cada ponto é um ensaio independente com essa probabilidade. Pela lei dos grandes números, a proporção de acertos aproxima-se de aa. A forma da região é indiferente, desde que se possa determinar se um ponto lhe pertence.

Que precisão se consegue?

O número de acertos segue uma distribuição binomial, pelo que a proporção H/NH/N tem desvio-padrão a(1−a)/N\sqrt{a(1-a)/N}. O erro típico diminui segundo 1/N1/\sqrt{N}: multiplicar o número de pontos por dez reduz o erro por um fator de cerca de 10≈3.16\sqrt{10} \approx 3.16. Para o reduzir a um décimo são precisos cerca de cem vezes mais pontos. Com um milhão, a margem para π ainda é de cerca de ±0.003. Não é necessário conhecer a área verdadeira para avaliar esta incerteza. Substituir aa pela proporção observada p^=H/N\hat p = H/N dá a margem ±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N} de um intervalo de confiança aproximado a 95%, usado aqui quando há pelo menos dez acertos e dez pontos fora do alvo. Se repetíssemos muitas vezes a experiência com o mesmo NN, cerca de um intervalo em vinte deixaria de fora o valor verdadeiro. A faixa azul no gráfico inferior representa o intervalo em torno do valor verdadeiro para cada NN em separado. A trajetória completa não tem de permanecer dentro dela, e numa só experiência os pontos adicionais podem até afastar temporariamente a estimativa do valor verdadeiro. É a margem que se estreita de forma previsível.

Quando compensa?

Para uma função suave de uma variável, uma regra determinista como a de Simpson (ver integração numérica) é muito mais precisa para o mesmo número de avaliações. A vantagem de Monte Carlo é que o expoente na sua taxa de convergência 1/N1/\sqrt{N} não muda com a dimensão. Em contrapartida, uma grelha com mm pontos por lado requer mdm^d pontos em dd dimensões. Em dimensão elevada, Monte Carlo pode por isso ser a melhor opção. Com alvos pequenos vê-se a sua limitação: o erro-padrão relativo à área é (1−a)/(aN)\sqrt{(1-a)/(aN)}. Uma região que ocupe um centésimo do quadrado exige muito mais pontos para a mesma precisão relativa.

Aspetos a observar

  • Os pontos aleatórios não ficam regularmente espaçados: com algumas centenas, é normal ver grupos de pontos e zonas vazias.
  • Os pontos provêm de um gerador pseudoaleatório com semente numérica, pelo que uma ligação partilhada reproduz os mesmos pontos. Ao atingir um milhão, «Lançar pontos» recomeça com a semente seguinte.

Temas relacionados