# Extension of Bayes' Theorem coin flipping example - finding a fair coin in a bag of biased coins

There's a fairly common example of Bayes' Theorem in which a coin is drawn from a population with a known amount of biased coins and fair coins. A coin is drawn, flipped a certain amount of times, and then one is challenged to determine the probability that the flipped coin was biased, resulting in a standard implementation of Bayes' Theorem.

I was thinking of an extension of this question, where the goal is to find a fair coin drawn from a population.

As a concrete example, suppose we have $$N$$ coins, of which $$n$$ are fair coins and the remainder will always flip heads. Our goal then is essentially to flip a tails so that we know we have a fair coin. Beforehand we decide after $$m$$ heads flipped from an individual coin, we will draw a new coin.

How would I approach the problem of calculating how many coins I would need to draw before reaching a certain probability threshold $$p$$ of having at some point flipped a tails?

In this case Bayes' Theorem tells us that the probability the first randomly chosen coin is biased after $$m$$ heads is given by:

$$\frac{\frac{N-n}{N}}{\frac{N-n}{N}+\frac{1}{2}^m*\frac{n}{N}}$$

My initial thought was to approach the problem in the vein of "how many coin flips do I need to have a probability $$p$$ of having flipped a heads?"-type problems and using Bayes' Theorem between each flip, but the examples of those questions that I've encountered require mutually independent events so I don't think that applies to this problem.

Additionally, would the question of finding an "optimal" $$m$$ be related to stopping time?

edit: After coming back to this question with a fresh mind, I had the thought that in the case there is only one fair coin (i.e. $$n=1$$) then we could say that the probability we would flip $$i$$ coins and not see a tails would be:

$$\frac{i}{N}*\frac{1}{2}^m+\frac{N-i}{N}$$

which would compute the probability that the fair coin was in the first $$i$$ coins drawn and that it was flipped $$m$$ times without seeing a tails, and add that to the probability that the fair coin hasn't yet been drawn. If this is valid, then I think I see how to extend it to $$n$$ fair coins (by summing over the different amounts of possibly drawn fair coins) as well as how to extend it to individual flips, but I'm also worried I'm violating some assumption in probability and intuiting something incorrectly. Would this work?

## 1 Answer

Start with $$N$$ coins of which $$n$$ are fair and $$N-n$$ always show heads.
Draw $$k$$ coin at random and flip each of them $$m$$ times.
The probability of not getting any tails is:
$$\sum_{i=0}^k P[\text{draw exactly } i \text{ fair coins}]\times \left(0.5^m\right)^i=\sum_{i=0}^k \frac{{n\choose i}{{{N-n}\choose {k-i}}}}{N \choose k}\times \left(0.5^m\right)^i$$
Now, find the smallest $$k$$ that makes this probability less than or equal to $$1-p$$. Then, the probability of seeing at least one tail will be at least $$p$$.