0
$\begingroup$

So this question is one of those "I'd rather ask and look stupid now than never know" types of questions.

It goes as follows:

The error in a Monte Carlo estimate is dominated by $\frac{C}{\sqrt(N)}$, where $C$ is an unkown constant and $N$ is the number of samples. A colleague believes that their Monte Carlo estimate, using M samples, provides an answer which is only accurate to within $10$% and the code takes $10^{-3}$ seconds to complete the calculation. They need to increase the number of samples to achieve $0.1$%. What is the new number of samples and how long will the calculation take?

So far I have the accuracy increase to be $99$% but I'm not sure this is correct. If it is, the sample size and time should also increase by the same percentage right?

I've written some code to emulate the problem and try and see emerically what might happen, but due to the random nature of the estimate (and the virtual PC I'm using), I'm not sure this helps.

Any thoughts?

EDIT: (again)

So now that I've had some time, drunk some coffee and relaxed my brain by watching some football and Two and a Half Men, I think I have the solution:

As stated below I need $\displaystyle \frac{C}{\sqrt N}=0.001$ - (1)

and I have $\displaystyle \frac{C}{100\sqrt M}=0.001$ - (2)

$\displaystyle \therefore$ from (1):

$\displaystyle C=0.001\sqrt N$

plug in to (2):

$\displaystyle \frac{0.001\sqrt N}{100\sqrt M}=0.001$

then:

$\displaystyle \sqrt N = \frac{0.1\sqrt M}{0.001}$

$\displaystyle \therefore N = 10000M$

and thus takes $\displaystyle (10000)10^{-3} = 10$ seconds.

For completeness, the question goes on to ask - How long would it take to achieve an accuracy of 0.001%?

My answer:

$\displaystyle (10^{8})10^{-3} \approx 28$ hours.

This is right now!

1 Answers 1

2

You're told the error is $C/\sqrt N$ and you're told the error is 10 percent (which is 0.1), and that gives you an equation. Write it down. You want the error to be one-tenth of 1 percent (which is .001), and your equation will tell you what you have to do to $N$ to achieve that. Once you know how $N$ has changed, you know how much the length of time changes, too.

  • 0
    Note: Question is now edited with the possible/probable answer.2012-05-02