# Approximating a probability from independent trials

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.
• 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? – user132290 Oct 7 '18 at 21:43
• @user132290 Maximize $f(p)=p(1-p)$ and evaluate if $f^{''}(p^*)<0$, where $f^{'}(p^*)=0$. – callculus Oct 7 '18 at 22:17
• @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? – callculus Oct 7 '18 at 23:52