Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.