# Number of samples needed in Monte Carlo simulation: how good is this approximation?

In Risk Theory Beard, Pentikanen and Pesonen (1969) mention a method of assessing number of samples needed for Monte Carlo simulation as

$$\sigma = \sqrt{\frac{p(1-p)}{s}} \leq \frac{1}{2} \sqrt{ \frac{1}{s}}$$

where $F(x) = p$, i.e. it is a probability of observing some value $x$ and $s$ is a number of samples. This shows us that with 99% confidence value we can expect that values observed in simulation study will lie $\pm 2.576 \sigma$ from $p$'s. This is similar to simulation standard error estimation based on observed variance mentioned by Aksakal. The authors seem to suggest that the formula can be used before the simulation to assess number of samples needed ($s$) to obtain simulated results with some precision of interest.

How good is this approximation?

• Which part? The normal approximation or the upper bound? – dsaxton Aug 6 '15 at 20:07
• Well, it depends on the (unknown) value of $p$. If $p$ is close to zero or one then the approximation is poor, but when $p = 1/2$ it's exact. – dsaxton Aug 6 '15 at 20:12
• But no matter what and how you simulate $p$'s..? This is quite a rough approximation... (Unless I misunderstood the brief description of the formula that was provided.) – Tim Aug 6 '15 at 20:13
• $p$ is not simulated, it's a true but known parameter. You would (presumably, the OP doesn't say) be simulating Bernoulli trials where the event either does or does not happen. The proportion of times it does is an estimate of $p$, and this is a way for determining a Monte Carlo sample size to get a certain margin of error without knowing $p$. – dsaxton Aug 6 '15 at 20:19
• @dsaxton it seems that the original description provided by the authors was misleading. If you could provide a little bit more detailed answer rather than a comment I would be inclined to accept it. – Tim Aug 6 '15 at 20:23

The approximation could be poor when $p$ is close to zero or one, but when $p = 1/2$ it holds exactly.

The idea here is that we want to estimate the probability of an event by using a sample proportion across many Monte Carlo trials, and we want to know how accurate of an estimate that proportion is of the true probability. The standard deviation $\sigma$ of a sample proportion is as the authors note $\sqrt{p (1 - p) / s}$ (where $s$ is the number of Monte Carlo simulations), but the problem is we don't know $p$. However, we can maximize $\sigma$ with respect to $p$ and get a conservative "estimate" of this standard error that will always hold no matter what $p$ happens to be. This may end up causing us to run more simulations than we need to, but this won't matter as long as the iterations themselves are computationally cheap.

This approximation is called Wald confidence interval. It's based on normal approximation of Binomial. How good is this approximation? There are two answers: when sample size is at least 30 and "it depends".

The "30" answer is very popular and has been propagated from book to book until it became an axiom, pretty much. Once I was able to track the first paper which mentioned it.

The "it depends" answer is explored in this paper: Central Limit Theorem and Sample Size by Zachary R. Smith and Craig S. Wells

The other thing is variance reduction. It is especially critical to use for low or high $p$. Obviously, Wald's formula will not work directly in this case.

• Thanks, it was clear for me that this is Wald's CI, the notation and description was somehow not clear but @dsaxton already managed to provide a perfectly clear clarification. – Tim Aug 6 '15 at 20:37
• Thanks for providing more details but in this case the $p$ parameter is unknown and we want to learn about the sample size, so the general fact about sample size and Wald does not seem to make here much difference - or doesn't it..? If it is so, please clarify :) – Tim Aug 6 '15 at 21:00
• @Tim, if I'm modeling rare events, I know that $p$ is low. So, I'll try to use some form variance reduction or stratified sampling. Think of an error in relative terms to $p$ in the formula. Small $p$ will have large relative error at the same number of simulations – Aksakal Aug 6 '15 at 21:03