Esta é uma tradução automática; o artigo original encontra-se em inglês. Ler o original
A aleatoriedade compra exatidão a uma taxa de câmbio terrível
Dez vezes mais amostras compram cerca de três vezes mais exatidão. Não dez. Essa taxa de câmbio é fixa e nenhuma astúcia a consegue renegociar.
Lançar dardos a um quadrado para medir π é a primeira demonstração habitual dos métodos de Monte Carlo. Conta-se a fração que cai dentro do quarto de círculo, multiplica-se por quatro e obtém-se uma estimativa.
O que a demonstração costuma omitir é o quão mal funciona.
Três predefinições e o que custam
Monte Carlo π inclui três tamanhos de amostra: 200, 2000 e 20000. Funcionam com uma semente fixa, pelo que não são anedotas: são os mesmos três números de cada vez que se abre a página.
- 200 pontos dão 3,040000, com um erro de 1,02 × 10⁻¹
- 2000 pontos dão 3,122000, com um erro de 1,96 × 10⁻²
- 20000 pontos dão 3,127800, com um erro de 1,38 × 10⁻²
Cem vezes mais trabalho entre a primeira e a última linha, e a resposta continua errada na segunda casa decimal. Ainda não conquistou o "3,14" que qualquer estudante sabe recitar.
A taxa é um sobre a raiz quadrada
Cada dardo é um ensaio independente de sim ou não, e o erro padrão de uma proporção medida a partir de n ensaios diminui como 1/√n. Para este estimador em particular, o erro típico é de 0,116 para 200 amostras, 0,0367 para 2000 e 0,0116 para 20000.
Assim, dez vezes mais amostras compram cerca de 3,16 vezes mais exatidão, porque 3,16 é a raiz quadrada de dez. Para ganhar um dígito decimal, um fator de dez em exatidão, é necessário um fator de cem em amostras. Para passar do erro de cerca de 0,037 com 2000 amostras para 0,0037, são necessários 200 000 dardos.
Vale a pena reter isto porque não se trata de uma propriedade de π, dos dardos ou desta implementação. É o teorema do limite central em ação: o erro da média de elementos independentes diminui com a raiz quadrada do número de elementos considerados, sejam eles quais forem. A mesma aritmética rege sondagens de opinião, contagens de eventos na física de partículas e todas as simulações executadas.
O que uma única semente não revela
Observem-se agora novamente os erros dessas três predefinições, pois não se comportam como a regra acaba de prometer. Passando de 200 para 2000, o erro diminuiu 5,19 vezes. Passando de 2000 para 20000, diminuiu apenas 1,42 vezes. Nenhum dos dois é 3,16.
Nada está errado. A lei da raiz quadrada descreve o erro típico, a largura da distribuição da qual a estimativa é extraída, e uma única execução é uma amostragem dessa distribuição. A execução de 2000 pontos por acaso ficou mais próxima do que o seu erro típico, a cerca de metade de um desvio padrão. A execução de 20000 pontos por acaso ficou mais afastada. A razão entre elas quase nada diz.
Esta é a interpretação errada mais comum de uma simulação. Uma execução que correu bem não é prova de um bom método, e uma execução que correu mal não é prova de um mau método. Não é possível ver a taxa a partir de uma semente; só é possível observá-la ao repetir e analisar a dispersão, que é o que o Normal Distribution descreve quando desenha essa dispersão sob a forma de uma curva.
Por que razão se tolera isto
Um método que exige um aumento de cem vezes no trabalho por dígito parece indefensável, e para problemas unidimensionais de facto é. A integração numérica comum numa grelha supera-o facilmente.
A razão pela qual o método de Monte Carlo domina a computação real é que 1/√n não faz qualquer menção à dimensão. Coloque-se uma grelha num problema em 20 dimensões com 10 pontos por eixo e são necessárias 10²⁰ avaliações. O método aleatório continua a precisar apenas do que 1/√n exige para a exatidão pretendida, e não quer saber se existem 20 eixos.
Assim, a taxa de câmbio é terrível e é também constante. Em dimensões reduzidas, deve ser recusada. Em dimensões elevadas, é frequentemente a única oferta disponível, razão pela qual a física, as finanças e a renderização a pagam.
Poisson é a mesma aritmética vista pelo lado da contagem: quando se contam eventos raros, a variância é igual à média, pelo que o erro relativo diminui novamente como um sobre a raiz quadrada da contagem. Duplicar a confiança numa taxa significa sempre quadruplicar a observação.