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?
 A: 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}$
A: 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} ).
$$
A: 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.
