The art of solving problems with Monte Carlo simulations

If N is the number of uniforms needed to have a sum bigger than 1, you can see that P(N>n)=P(S_n<1).

P(S_n<1) is not too bad to compute, or you can wikipedia it (Irwin-Hall distribution) to find the expression P(S_n<1)=1/n!

Combining the things, E[N]=sum(P(N>n),n=0..infinity)=sum(1/n!,n=0..infinity)=exp(1).

One solver in particular submitted several elegant solutions: http://math.uchicago.edu/~timblack/blog/addtoone.html

The curse of dimensionality means you often need a huge number of samples to guarantee a useful level of precision. Additionally, many quantities you'd like to know come up in Monte Carlo simulations themselves. That creates an intractable O(N^2) problem.

Here's an example that I encountered at work yesterday:

You want to know P(x>=a and y>=b) where (x,y) is a standard bivariate normal with correlation R.

You can:

1. Simulate a bunch of (x,y) and take the mean of the indicator function 1[x>=a, y>=b]. This will take whole seconds to compute.

2. Use an adaptive quadrature method like scipy.integrate.nquad. This will take dozens to hundreds of milliseconds.

3. Write a fixed grid Gauss-Legendre quadrature routine in c. This will take less than a microsecond.

I needed this value inside a Monte Carlo simulation. If I had to simulate the solution, the problem would be intractable.

Also if you’re plugging random numbers directly into the simulator like this article does, the convergence rate will be n^(1/2) which means that going from 8 digits of precision to 10 digits will take 10,000 times longer. In order to get a better convergence rate, you could use jittering/stratification or a low-discrepancy sequence instead of a bare random number generator. Even with a perfect QMC convergence rate of 1/n, getting 10 digits of precision reliably will take 100 times longer than 8 digits of precision.

I don’t remember the chip defect problem, so I’m not sure whether I solved it. ;) But based on your description, and knowing that Euler problems are designed to be resistant to long computations, I might bet on the convergence rate being the issue. I saw your comment about using a better RNG, but if you used a 64-bit RNG, I doubt that is the problem, I think you’d get away with a low quality RNG if you waited long enough.