# Computing the expected value using the sample mean gives poor convergence?

This is for Project Euler problem #371:

http://projecteuler.net/problem=371

My solution was to generate a huge random pool of numbers between 0 and 999 inclusive, repeatedly ask the question 'How many numbers do I need to pull into a holding area before I get a pair that adds to 1000?', and then average the resulting list(to get the expected number of plates).

The problem is that hand-optimizing my program lets me crunch about 10 million samples of the second step(so a total pool of 400 million random numbers are used), but I'm not even getting 2 digits of accuracy behind the decimal(I'm using exact integer arithmetic):

• 39.6638047
• 39.6791329

There could be an error in my program otherwise, but I'm not asking you to debug my program. I'm sure there's a better way to do this in principle than brute-forcing it with the Law of Large Numbers, so I wanted to ask:

• Should I be expecting more than 2 digits of precision with my approach?

• If someone handed you a huge number of random samples, how would you efficiently compute their expected value to a high precision?

-
For rare events, it is inefficient to simulate from the distribution of reference $F$, because it induces a large variance. Importance sampling is better: pick a distribution $G$ that concentrates more on the event of interest and use the weights $F(X_i)/G(X_i)$ in your average. A good choice of $G$ may reduce the variance to huge extents. – Xi'an Feb 15 '12 at 11:04
For the Monte Carlo method, the digits of precision depend both on the variance of the estimated function and on the number of simulations $N$. It decreases as $1/\sqrt{N}$ but with a constant that depends on the problem. – Xi'an Feb 15 '12 at 11:07