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?

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.
