Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Still baffled I'm afraid. I have the following (my brain needs sleep): $\displaystyle C/\sqrt(M) = 0.1 => C/100\sqrt(M) = 0.001$ Which leads me to believe you square M and multiply by 100 to get $\displaystyle N = 100M^2$ and thus the time is increased in the same way, thus $\displaystyle 100(10^{-3})^2 = 3.16 seconds$? –  Billy Ray Valentine Apr 23 '12 at 15:33
    
Let's start at the end; $100(10^{-3})^2\ne3.16$. Now go back a bit: you have $C/(100\sqrt M)=0.001$, and you want $C/\sqrt N=0.001$, from which you can get a relation between $N$ and $M$ (and it's not $N=100M^2$. –  Gerry Myerson Apr 24 '12 at 1:48
    
Sorry, I meant the root of M x 100, but that's still probably wrong. Will investigate now as I have more time. Cheers. –  Billy Ray Valentine Apr 24 '12 at 8:57
    
Note: Question is now edited with the possible/probable answer. –  Billy Ray Valentine May 2 '12 at 23:17
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.