I am running simulations for a particular problem, which is not relevant to my question. Every simulation takes non-trivial amount of time and its result is binary - either 0 or 1, with probabilities $1-p$ and $p$ respectively. If I run $N$ simulations and get $x$ $1$'s, then $\frac{x}{N}$ is my approximation of $p$. My question is - which theorem/inequality is most commonly used to decide how big $N$ should be to be quite certain my error isn't too big? Does the answer change if I add additional information about $p$ (for example $p > 0.01$ and $p < 0.99$)? Obviously I would like $N$ not to be too big, to minimise running time of my simulations while still being quite certain that my approximation is accurate enough.


The standard deviation after $N$ trials is$\sqrt{\frac{p(1-p)}{N}}$. Since you have only an estimate for $p$, use $N-1$ rather than $N$ for estimating standard deviation. You need to decide how small the standard deviation has to be to satisfy your requirement.

The formula is from Bernoulli trials.

  • $\begingroup$ Thank you, that is very useful. How can I intuitively understand the fact that the standard deviation is the highest at $p = \frac{1}{2}$ and gets smaller and smaller with p? $\endgroup$ – user132290 Oct 7 '18 at 21:43
  • $\begingroup$ @user132290 Maximize $f(p)=p(1-p)$ and evaluate if $f^{''}(p^*)<0$, where $f^{'}(p^*)=0$. $\endgroup$ – callculus Oct 7 '18 at 22:17
  • $\begingroup$ I am not asking how to show it, that is trivial. I am asking about how to think about it in intuitive terms. $\endgroup$ – user132290 Oct 7 '18 at 23:15
  • $\begingroup$ @user132290 $f(p)=p(1-p)$ is a parabola. Since $a=-1$ is negative the parabola opens downward. Therefore there exists exatly one maximum and no minimum. The value of $p^*$ is in the middle of $p=0$ and $p=1$ (roots). Better now? $\endgroup$ – callculus Oct 7 '18 at 23:52
  • $\begingroup$ When p is near 0 or near 1 the distribution tends to have a narrow width. In the extreme case, p=0 or p=1, there is no width at all. $\endgroup$ – herb steinberg Oct 8 '18 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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