Let's say that there is a coin and I don't know what it's p is (what the probability of flipping heads is) — basically, I have no info on whether it is biased/unbiased to what degree.
On average, after how many flips will I be able to make an estimate of p that is statistically significant?
I can only think of one way of doing this, but it's super unwieldy. I would have to calculate the P(coin is biased with p = x | current flip outcomes) for all x from [0, 1], and wait till this number comes to > .95.
There are different ways to construct an interval estimate for a binomial proportion; therefore, the answer depends on the choice of estimator.
For instance, the Wald interval is given by $$\hat p \pm z^*_{\alpha/2} \sqrt{\frac{\hat p(1-\hat p)}{n}},$$ where $\hat p$ is the observed proportion of successes (which we may arbitrarily take to be the proportion of heads), $n$ is the sample size, and $z_{\alpha/2}^*$ is the upper $\alpha/2$ percentile of the standard normal distribution, thus for a confidence level of $95\%$, we have $z_{\alpha/2}^* \approx 1.96$. Then in order for the margin of error to be below some prespecified error level, say $\epsilon/2$, we must have $$n \ge \left\lceil \left(\frac{z_{\alpha/2}^*}{\epsilon}\right)^2 4\hat p(1-\hat p)\right\rceil.$$ Since $\hat p$ is observed only after the specified number of trials is performed, the lower bound for $n$ for all $\hat p \in [0,1]$ occurs when $\hat p (1 - \hat p)$ is as large as possible; i.e., $\hat p = 1/2$, thus $$n \ge \left\lceil \left(\frac{z_{\alpha/2}^*}{\epsilon}\right)^2 \right\rceil$$ ensures that for any value of $p$ (and in turn, $\hat p$), the resulting $n$ will yield a $100(1-\alpha)\%$ Wald confidence interval that has width not exceeding $\epsilon$. However, when $\hat p$ is close to $0$ or $1$, the resulting confidence interval may be substantially smaller than $\epsilon$.
But as I have already stated, there are different ways to compute an interval estimate. The Wald interval is computationally simple but does not, in general, attain the nominal coverage probability. The Wilson score interval, or the Clopper-Pearson exact interval, address this issue. The latter guarantees the nominal coverage probability, but at the expense of potentially very large intervals.
The width of the Wilson score interval is given by $$2 \frac{z_{\alpha/2}^*}{1 + (z_{\alpha/2}^*)^2/n} \sqrt{\frac{\hat p(1-\hat p)}{n} + \frac{(z_{\alpha/2}^*)^2}{4n^2}}.$$ Solving this for $n$ in terms of the desired width $\epsilon$ gives a rather nasty quadratic, but as in the Wald case, the maximum width is attained when $\hat p = 1/2$, thus the result simplifies to $$n \ge \left\lceil (z_{\alpha/2}^*)^2 (\epsilon^{-2} - 1) \right\rceil.$$ This demonstrates that this interval is slightly smaller than the Wald.
The Clopper-Pearson interval is not straightforward to compute the minimum sample size needed; as such, we do not compute it.