Uncertainty calculation for calculating pi using Monte Carlo integration

[googlygluon]

Homework Statement

I wrote a code that calculates pi using accept&reject monte carlo integration. It picks -1000000000 pseudo-random points (x,y), and counts the number of points that fall within a unit circle (let's call that number k).

The ratio of k/ N (N = Number of trials = 1000000000) is equal to pi / 4 (the area of the circle / the area of the square around it).

I wish to find the variance so that I may present my result as 3.14158 +- [uncertainty].

The Attempt at a Solution

Now, since this is a random (pseudo random really, but anyway) process, the uncertainty should be 1 / sqrt(N). Am I mistaken? Do I have to calculate the variance for both x and y and use error propagation? Thanks in advance.

 

[Mute]

The best way to estimate the uncertainty on your measurement would be to run the program several times, for various random seeds. This will give you a series of measurements of \pi, which you can then compute the mean and standard deviation of. The standard deviation should scale as the inverse square root of the number of trials.

 

[singhvi]

The most exact way would be to use probability (assuming a true random uniform generator). Calculate the probability of finding a particular value of 'pi', the value where the probability falls to 1/e or 1/2 can be used as your error.

To calculate this probability, you can use the known probability of a random point being outside or inside the circle. For eg. with n random points, the probability of finding the value of pi as zero would be the case where all points fall outside, probability being (1 - area of circle/total area)^n

For other values there will be more than one case, but you should be able to generalize it and find an expression for any particular value of pi.

Note: when I say probability, I mean relative probability, relative to probability of getting value as 'pi'.

 

[ideasrule]

Now, since this is a random (pseudo random really, but anyway) process, the uncertainty should be 1 / sqrt(N). Am I mistaken? Do I have to calculate the variance for both x and y and use error propagation? Thanks in advance.

The uncertainty scales as 1/sqrt(N), but the proportionality factor is not 1.

We're trying to find the standard deviation of a binomial distribution with n samples, where the two outcomes are "inside the circle" and "outside the circle". It's just sqrt(npq), where p is the probability of a certain point being inside the circle (which is pi/4), and q is the probability of the point being outside.

This means that, with n samples, n*pi/4 +- sqrt(npq) will be inside the circle. Dividing the equation by the relevant constant will give you the right bounds on pi.

 

[L-x]

The best way to estimate the uncertainty on your measurement would be to run the program several times, for various random seeds. This will give you a series of measurements of \pi, which you can then compute the mean and standard deviation of. The standard deviation should scale as the inverse square root of the number of trials.

Bear in mind that this is the only method mentioned above which doesn't require you to already know the value of pi.

 

[googlygluon]

Thanks everyone, I appreciate your help.