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?

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