Finding probability of an unfair coin

An unfair coin is tossed giving heads with probability $p$ and tails with probability $1-p$. How many tosses do we have to perform if we want to find $p$ with a desired accuracy?

There is an obvious bound of $N$ tosses for $\lfloor \log_{10}{N} \rfloor$ digits of $p$; is there a better bound?

-
Can you explain the obvious bound? I'm curious. –  GWu Apr 13 '11 at 14:35
@GWu: $\lfloor\log_{10}{N}\rfloor$ is how many decimal digits number $1/N$ has. It is also how much a $N$th toss will influence your knowledge of $p$. –  Eelvex Apr 13 '11 at 15:18

This is a binomial distribution. The standard deviation on the number of heads is $\sqrt{Np(1-p)}$, so leaving aside the difference between your measured $p$ and the real $p$ you need $N \gt \frac{p(1-p)}{accuracy^2}$

-
But I don't know $p$; I want accuracy as a function of $N$ only. –  Eelvex Apr 13 '11 at 14:24
@Eelvex: The function is maximised when $p=1/2$ so use that. If you want accuracy to mean $k$ standard deviations rather than just 1, take $N > \left(\dfrac{k}{2 \times \text{accuracy} }\right)^2$. –  Henry Apr 13 '11 at 14:49

There is no way to find $p$ by tossing the coin with an accuracy like for the deterministic problems. That's a Monte-Carlo simulation and hence you better use bounds for these methods. Note that these bounds are probabilistic. E.g. $$\mathsf{P}(|p-\hat{p}_n|>\delta)\leq 2\mathrm{e}^{-2n\delta^2}$$ where $\hat{p}_n$ can be obtained as a frequency of heads from tossing the coin $n$ times, i.e. $$\hat{p}_n = \frac{1}{n}\#( \text{heads in the tossing sequence} ).$$

-

Your 'obvious bound' is incorrect. You cannot place absolute bounds on the value of p, regardless of the size of N.

However, as you increase N, your confidence improves in your calculated $p=N_{heads}/N$. Theoretically, though improbably, you could get 250 heads from 1000 throws of a fair coin.

You need to carry out a hypothesis test under the binomial distribution using a confidence interval of your choosing.

-