# Monte Carlo method error in Bernoulli random variables

Assume I am flipping an unfair coin. Flipping the coin will be heads with probability $p$ and tails with $1-p$. I have no idea what $p$ is (it could even be $.5$!)

Let's say I decide to use the Monte Carlo method to approximate $p$. Let's say my results are:

trials | heads
--------------
10  |    4
100  |   39
1000  |  381
10000  | 3754


Assume for the moment that $p_{actual} = \frac{3}{8}$. In the case of $10000$ trials, $p_{observed} = \frac{3754}{10000}$

1. Is there a formula for determining, say, 95% confidence in $p_{observed}$ as my number of trials goes up?
2. Can I calculate the expected error rate (i.e. $|p_{observed} - p_{actual}|$) for a given number of trials?
• You can do it even without assuming any knowledge of p. Besides, the confidence or absolute error will be guaranteed to be better than the computed value (that is, you will get a bound, not just an approximation). For that, use inverse binomial sampling. See the answer to this question – Luis Mendo Jan 1 '14 at 3:58

Yes, a simple $100(1-\alpha)\%$ confidence interval can be furnished for large sample sizes using a normal approximation; for instance, $$\hat p \pm z_{1-\alpha/2}^* \sqrt{\frac{\hat p (1-\hat p)}{n}},$$ where $\hat p$ is your $p_{\rm observed}$, the point estimate of the parameter $p$. This is not a good approximation when $p$ is close to $0$ or $1$, or when $n$ is small. In such a case, we can use alternative intervals, e.g., the Wilson score interval, or the exact binomial proportion interval using the $F$-ratio distribution. There is extensive literature on this topic.
(Incidentally, $z_{1-\alpha/2}^*$ is the $1-\alpha/2$ quantile of the standard normal distribution; i.e., it satisfies $\Pr[Z \le z_{1-\alpha/2}^*] = 1 - \alpha/2$.)
For the answer to your second question, yes, we can calculate ${\rm E}[|\hat p - p|]$, since $\hat p = X/n$, where $X \sim {\rm Binomial}(n,p)$. I don't know the result off the top of my head.
Addendum. It would seem that the sum $$\sum_{x=0}^n \left|\frac{x}{n} - p\right| \binom{n}{x} p^x (1-p)^{n-x}$$ doesn't have a nice closed form. However, the squared error of course does; it is simply the variance: $${\rm E}[(\hat p - p)^2] = \frac{p(1-p)}{n}.$$