How to determine the number of coin tosses to identify one biased coin from another?

If coin $X$ and coin $Y$ are biased, and have the probability of turning up heads at $p$ and $q$ respectively, then given one of these coins at random, how many times must coin A be flipped in order to identify whether we're dealing with coin $X$ or $Y$? We assume a 0.5 chance that we can get either coin.

In @LoganHodgson's (+1) notation, it is a little risky to use a normal approximation unless $p$ and $q$ are close enough to $1/2$ that $np, n(1-p), nq$ and $n(1-q)$ are all larger than 5 or so, whatever $n$ turns out to be.

My own version of the computation for a normal approximation is to say we are comfortable with a 5% error probability and then to say that for some cutoff point $c,$ we would like to have $P(X \le c) \ge .95$ and $P(Y \le c) \le .05.$

It might be best to pick $c$ very precisely as @DjuraMalenkov's $m,$ but I think it is not far off in practice to pick $c$ as halfway between the two binomial means as $c = (np + nq)/2.$ Also, let $\delta = |p - q|.$

In terms of a normal approximation for $X,$ we want $\mu + 1.645\sigma$ to be below $c$. With $\mu = np$ and $\sigma = \sqrt{np(1-p)}$ and some algebra this amounts to $n = 1.645^2p(1-p)/\delta^2 = 2.71p(1-p)/\delta^2.$ A similar argument for $Y$ gives a similar result with $q$.

Two examples: if $p = .3$ and $q = .7,$ this interpretation of the normal approximation gives $n \approx 17;$ for $p = .4$ and $q = .5,$ we get $n \approx 271.$

Let's see how well these approximations hold up under exact binomial computations. The R code below does a grid search for the smallest $n,$ called n.min, giving 5% error on both sides of $c,$ prints a table of relevant results for nearby values of $n,$ and makes bar charts of the two binomial distributions to illustrate the overlap.

 p = .3;  q = .7  
 n = 1:10000;  c = n*(q + p)/2
 cond = (pbinom(c, n, p) >= .95 & pbinom(c, n, q) <= .05)
 n.min = min(n[cond]);  n.min
 ## 17
 cbind(n, c, pbinom(c,n,p),  pbinom(c, n, q), cond)[(n.min-2):(n.min+7),]
     n    c                      cond
 ## 15  7.5 0.9499875 0.05001254    0
 ## 16  8.0 0.9743265 0.07435155    0
 ## 17  8.5 0.9597231 0.04027694    1
 ## 18  9.0 0.9790320 0.05958588    0
 ## 19  9.5 0.9674466 0.03255336    1
 ## 20 10.0 0.9828552 0.04796190    1
 ## 21 10.5 0.9736101 0.02638994    1
 ## 22 11.0 0.9859649 0.03874479    1
 ## 23 11.5 0.9785520 0.02144800    1
 ## 24 12.0 0.9884977 0.03139365    1

x = 0:n.min; pdfp = dbinom(x, n.min, p); pdfq = dbinom(x,n.min,q)
mlb = paste("BINOM(",n.min,", ",p,") and BINOM(",n.min,", ",q,")", sep="")
plot(x-.1, pdfp, type="h", ylab="PDF", xlab="Successes", 
     ylim=c(0, max(pdfp,pdfq)), col="red", main=mlb)
  lines(x+.1, pdfq, type="h", col="blue")
abline(v=c[n.min], lty="dotted"); abline(h=0, col="green2") 

In the table 1s signify that the condition about 5% errors has been met. Because of the discreteness of the binomial distributions and the rough way we picked $c,$ we have $n = 17$ as the smallest valid sample size, but notice that $n = 18$ doesn't exactly work, and that values $n \ge 19$ do work. But $n = 17$ happens to match the value from the normal approximation. [I include the R code for the graph in case someone wants to experiment with it.]

Here, without further detailed comment, are the table and the plot for the example with $p=.4$ and $q=.5,$ where the normal approximation also works reasonably well.

##   n      c                      cond
## 266 119.70 0.9488177 0.04882243    0
## 267 120.15 0.9558623 0.05569961    0
## 268 120.60 0.9507442 0.04945401    1
## 269 121.05 0.9575457 0.05637062    0
## 270 121.50 0.9526008 0.05008491    0
## 271 121.95 0.9472245 0.04438981    0
## 272 122.40 0.9543900 0.05071511    0
## 273 122.85 0.9491926 0.04498017    0
## 274 123.30 0.9561140 0.05134455    0
## 275 123.75 0.9510903 0.04557024    1

Some factors to think about:

1. How different are the probabilities?
2. How sure do we want to be?

If the probabilities of heads are close together, like $p=.501$ and $q=.500$, it will take many trials to really see any difference, but if the probability of heads are drastically different, like $p=.9$ and $q=.4$, fewer trials are needed.

All we need is to tell if our statistical significance overlaps at all.

Doing the math:

Mean number of heads for X->$n*p$ | Standard Deviation X$=\sqrt{n*p*(1-p)}$

Mean number of heads for Y->$n*q$ | Standard Deviation Y$=\sqrt{n*q*(1-q)}$

In order to determine if we have one coin, we need to be sure we DON'T have the other coin. If we do enough trials and our head success count is outside of our allowed parameters, we decide it is the other coin.

For example, X has probability $.3$, Y has probability $.6$. We will use an $a=.05$ significance value. Therefore,

Mean X$=.3n$

Standard Deviation X$=\sqrt{.3n*(1-.3)}\approx.46\sqrt{n}$

We run $n$ trials and get a proportion $g$.

test$=$normalpdf$(.3*n,.46*\sqrt{n},g*n)$

If this test probability is more than $.05$, we can determine with an $a=.05$ significance that the coin's bias is not different enough from coin X's bias to prove that the coin is not coin X.

But if the test probability is more than $.05$, we fail to prove with an $a=.05$ significance that the coin's bias is different enough from coin X's bias to not be coin X.

Does this help?

If you know beforehand that $p=1$ and $q=0$ or vice versa then one flip is enough.

If you know beforehand that $p=1$ and $0<q<1$ you will almost certainly find out, but it may take an "infinitely" long time (i.e., for any given $n$, the probability that it takes at least $n$ flips is non-zero).

In the general case where $0<p<1$ and $0<q<1$ you will never know for sure, as both coins may produce any possible series of flips. As others have mentioned, you can achieve some degree of (bayesian) certainty, but you can never be certain.

We should find the percentage of heads that is equally probable for both coins, let that be $m\in(0,1)$ Let say $p<m<q$. So we have: $$p^m(1-p)^{1-m}=q^m(1-q)^{1-m}\\ (\frac p q)^m(\frac {1-p}{1-q})^{1-m}=1\\ (\frac {p(1-q)} {q(1-p)})^m=\frac {1-q}{1-p}\\ m=\log_{\frac {p(1-q)} {q(1-p)}}\frac {1-q}{1-p}$$ We are looking for such $n$ that probability that number of heads is bellow $mn$ when you picked X, is for $P$ larger than same probability if you picked Y. Where $P$ is the wanted accuracy for claiming which coin it is.

$p_n(k<mn|X)-p_n(k<mn|Y)>P$
Which also implies
$p_n(k>mn|Y)-p_n(k>mn|X)>P$

For finding $p_n(k<mn|X)$ we can use approximation to standard Normal distribution, it will be $$\Phi(\sqrt n\frac{m-p}{\sqrt{p(1-p)}})-\Phi(\sqrt n\frac{m-q}{\sqrt{q(1-q)}})>P$$ So problem becomes: find $x$ such that $\Phi(ax)-\Phi(bx)>P$ where $a,b,P$ are known