Saltar al contenido ForoHackers

Monte Carlo and the 1/sqrt(N) wall

Física computacionalProbabilidad y estadísticaSimulación y modelado
#1136 · quantum_tunnel_rat · · Denunciar

The most famous Monte Carlo toy: estimate pi by throwing random points in a unit square and counting how many land inside the quarter circle.

import random

def pi_estimate(n):
    inside = 0
    for _ in range(n):
        x, y = random.random(), random.random()
        if x * x + y * y < 1.0:
            inside += 1
    return 4.0 * inside / n

for n in (100, 10_000, 1_000_000):
    print(n, pi_estimate(n))

Typical output is something like 3.2, 3.14, 3.1415, with errors in the next digit. The key fact is how the error behaves: it shrinks like 1/sqrt(N). To gain one more correct decimal digit you need 100 times more samples. To gain two, 10000 times.

That sounds terrible, and for a 2D integral it is: simple quadrature rules beat it by a mile. But the rate does not depend on the dimension. A grid with 10 points per axis in 10 dimensions needs 10^10 points, while Monte Carlo still gives 1/sqrt(N). That is why it is the workhorse for high-dimensional integrals in physics, chemistry and graphics.

It also tells you honestly how good your answer is: the spread across independent runs is the error bar. If someone gives you a Monte Carlo number without one, ask for it.

#1871 · bayes_and_bagels · · Denunciar

The error bar point cannot be stressed enough. The standard error here is sqrt(p(1-p)/N) times 4, where p is pi/4, so about 1.64 / sqrt(N). For a million samples, the 1-sigma error is about 0.0016. If your million-sample run says 3.1416 and you are astonished, you are just lucky.

#1872 · gradient_descent_hiker · · Denunciar

Quasi-random sequences (Sobol, Halton) improve the rate for smooth integrands towards roughly 1/N, at the cost of losing the clean statistical error bar. Different tool, different promises.

#1873 · quantum_tunnel_rat · · Denunciar

Right on both. The bonus question: if you need the error bar from a quasi-random run, you randomise it (random shifts, scrambling) and repeat. Which gives you back an honest spread, with a better constant.

Inicia sesión o únete para responder.