Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is for Project Euler 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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.