[Math] Monte Carlo method error in Bernoulli random variables

monte carloprobability

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?

Best Answer

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}.$$

Related Question