8
$\begingroup$

I have two very biased coins:

  1. The first coin (C1) lands on heads 95% of the time.
  2. The second coin (C2) lands on heads only 1% of the time.

One of the coins has been selected and I want to determine which coin that is. I can toss the coin as many times as possible and record a series of heads and tails results.

Let's say I want to know with 99.99% confidence, and as soon as possible, which coin is being flipped. How can I do so?

I would like to flip the coin, and after each result either continue or make a decision on which coin I have. I don't need to know how many times to flip before I start.

(Sorry if this is a very basic question that has been asked before. I lack the vocab to know how to search for this problem).

$\endgroup$
9
  • $\begingroup$ I don't have time to answer, but this is an awesome question. $\endgroup$ – Cam.Davidson.Pilon Sep 25 '20 at 1:15
  • 1
    $\begingroup$ Sounds like a task for a sequential probability ratio test which is known to have (on average) the smallest number of trials to reach a decision. $\endgroup$ – Dilip Sarwate Sep 25 '20 at 1:50
  • $\begingroup$ This feels like a homework question. Is this self-study? $\endgroup$ – EngrStudent Sep 25 '20 at 2:02
  • $\begingroup$ It's not a homework question. It is related to my work but rewritten using coins. $\endgroup$ – WW. Sep 25 '20 at 2:54
  • $\begingroup$ There are two kinds of valid answers to this question, depending on what you mean by "as soon as possible:" would that mean (1) you wish to determine a minimal but fixed sample size that will produce a correct decision with a chance of 99.99% or (2) you wish to have a sequential decision procedure that will tell you when to stop flipping, as well as tell you which coin it is with 99.99% accuracy, that yields a minimal expected number of flips? The latter value is going to be less than the former, but in (2) you risk having to flip a long time in rare cases. Which is it? $\endgroup$ – whuber Sep 25 '20 at 14:11
6
$\begingroup$

Say the odds of getting $C_1$ over $C_2$ are, in principle, $1:1$. Then, you flip the coin $n$ times and get $x$ heads. If we call the probabilities of heads $p_1=0.95$ and $p_2=0.01$, then the probability that each coin gives $x$ heads is:

$$P(x|C_1)=p_1^x(1-p_1)^{n-x}$$

$$P(x|C_2)=p_2^x(1-p_2)^{n-x}$$

If we use Bayes theorem, we get the odds that the coin is $C_1$ including the information from the coin tosses:

$$\begin{align} \frac{P(C_1|x)}{P(C_2|x)}&=\frac{P(C_1)\cdot p_1^x(1-p_1)^{n-x}}{P(C_2)\cdot p_2^x(1-p_2)^{n-x}}\\ &=\frac{p_1^x(1-p_1)^{n-x}}{p_2^x(1-p_2)^{n-x}}\\ &=\left(\frac{p_1}{p_2}\right)^x\left(\frac{1-p_1}{1-p_2}\right)^{n-x} \end{align}$$

For example, if you tossed the coin 3 times and had 2 heads, you would have:

$$\frac{P(C_1|x)}{P(C_2|x)}=\left(\frac{0.95}{0.01}\right)^{2}\left(\frac{0.05}{0.99}\right)^{1}\approx456$$

That means the odds that the coin is $C_1$ are $456:1$, which is equivalent to a probability of $\frac{456}{456+1}\approx99.8\%$. That looks like a huge value for such a low number of trials, and the reason is that the probabilities $95\%$ and $1\%$ are very different. If the coins had closer probabilities, the odds would not be so dramatic.

$\endgroup$
5
  • $\begingroup$ Thank you for this answer. It has made me realise that a more accurate description of my problem includes that C1 is much more common than C2. So we could say I have a bag of 100 x C1 and 1 x C2 and I want to detect the C2 coin. $\endgroup$ – WW. Sep 25 '20 at 3:15
  • 1
    $\begingroup$ @WW In that case P(C1) and P(C2) change, but the approach remains the same. $\endgroup$ – Demetri Pananos Sep 25 '20 at 4:51
  • $\begingroup$ How does Bayes' theorem apply here, since there is no prior distribution?? $\endgroup$ – whuber Sep 25 '20 at 14:08
  • $\begingroup$ @whuber there is a prior distribution, given by $(P(C_1),P(C_2))$. I assumed the prior odds were 1:1, therefore they cancelled when finding the posterior odds. It was a rather arbitrary assumption though, and the OC's comment indicates that it would be better to use 100:1 prior odds $\endgroup$ – PedroSebe Sep 25 '20 at 17:43
  • $\begingroup$ There is no prior distribution mentioned in the question. Indeed, it's not necessarily the case that there is any relevant distribution. $\endgroup$ – whuber Sep 25 '20 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.