15
$\begingroup$

This question stems from a children's board game where if you succeed in flipping all heads after three attempts you can perform the desired action, and if not then your opponent gets to perform their desired action. Now for the problem:

Flip three coins. If you get any heads, set them aside and flip the remaining coins. Again, if you get any more heads, set them aside and try one more time. The ultimate objective is to have all three coins flipped to heads after the three total attempts. Remember, any coins that are flipped to heads are set aside so that subsequent attempts only need to done using the coins that previously flipped "tails". What is the probability of achieving three "heads" in the allotted three attempts?

Please give me a hint regarding the answer, and do not provide the actual answer. This is for self-study and I've been working through the solution as best I can.

Here's what I've attempted so far:

  1. Count up the total number of "success" paths and "failure" paths, then divide the total number of success paths by the total number of paths. This comes out to 9/18, which is 50%. This seems correct based on my experience playing the game, but it doesn't seem right based on the fact that each path does not have the same probability of occurring. For example, flipping three heads on the first try is (1/2 * 1/2 * 1/2) = 1/8, but multi-flip flows that are less likely than that to happen.
  2. Compute the total probability by adding the individual probabilities of each “success” path. This is consistent with how I understand how to approach these types of problems using OR/AND appropriately. However, the end result of my computation is (1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/512 + 1/128 + 1/512) = ~25%, which is seemingly lower than how this behaves in practice. More on this math below.

Here are the various ways in which each path can occur as well as the probability of each occurring. I'm putting this here for you to understand my thought process, as well as to be able to determine if this is where I'm making a mistake:

 1. HHH = (1/8)
 2. HHT, H = (1/16)
 3. HHT, T, H = (1/32)
 4. HTT, HH = (1/32)
 5. HTT, HT, H = (1/64)
 6. HTT, HT, T = (1/64)
 7. HTT, TT, HT = (1/128)
 8. HTT, TT, HH = (1/128)
 9. HTT, TT, TT = (1/128)
10. TTT, TTT, TTT = (1/512)
11. TTT, TTT, TTH = (1/512)
12. TTT, TTT, THH = (1/512)
13. TTT, TTT, HHH = (1/512)
14. TTT, TTH, TT = (1/256)
15. TTT, TTH, TH = (1/256)
16. TTT, THH, T = (1/128)
17. TTT, THH, H = (1/128)
18. TTT, HHH = (1/64)

One thing I'm trying to keep in mind is that the probabilities of all possible paths should equal 1, which is not true in the above case (~.35). So that's an indication that I haven't computed these individual probabilities correctly.

Thanks in advance for your help! If I can supply more detail, please let me know in a comment and I would be happy to update this question. I'll reiterate that I'm not necessarily looking for someone to hand me the solution — I'm willing to work for it with a little guidance.

$\endgroup$
  • $\begingroup$ I had to stop at the outset because I cannot determine what exactly you mean by "make it all the way through this flow." Could you please edit your post to clarify your meaning? It sounds like you want to know the chance of repeating, three times in succession, the feat of producing at least one heads in three flips; but in light of your preface about flipping three heads in a row that doesn't sound right. $\endgroup$ – whuber Oct 5 at 21:38
  • $\begingroup$ Okay, I attempted to clarify the problem statement. Does that read any better? $\endgroup$ – Bryan Larson Oct 5 at 22:09
  • $\begingroup$ In some of your paths, when tossing two coins in the second round, you seem to calculate the possibility of HT as 1/4. You correctly figured that HH and TT are both 1/4, which should tell you that the remainder must be a half - this is because HT and TH are both 1/4 possibilities. Likewise when you still have two coins left for the third flip. Hopefully this helps you correct your calculations here. $\endgroup$ – AdamV Oct 6 at 8:22
  • 4
    $\begingroup$ This is a question-and-answer site, with the goal that each contribution (from both the questioner and the answerers) can ideally be of value to future people with the same problem. Asking not to be provided an answer turns this into a personal tutorial for the OP, which seems completely counter to the purpose of StackExchange. $\endgroup$ – Michael MacAskill Oct 6 at 22:33
  • $\begingroup$ Probably easier to calculate the probability it doesn't happen and subtract that from 1. $\endgroup$ – Carl Witthoft Oct 7 at 13:50
23
$\begingroup$

There is a slightly easier approach. Since you asked not to be given the answer, here are some hints:

  • In effect you flip each coin up to three times. If it comes up heads on any of those then you stop with that coin

    • What is the probability you get three tails with a particular coin?
    • So what is the probability you get that coin showing heads in the up-to-three attempts?
  • Each of the three coins is independent of the other.

    • So what is the probability you get all three coins showing heads in the up-to-three attempts?

As a check, you should have an answer with denominator $2^9=512$ and a final answer close to by not exactly $\frac23$

| cite | improve this answer | |
$\endgroup$
11
$\begingroup$

The answer by Henry +1 (and others as well) is much simpler. However, the method below is more general. If the problem is changed slightly, for instance that the probability of a coin landing heads becomes dependent on the number of coins being flipped, then the simple answer does not work anymore.


I would model this with a Markov chain. Giving a matrix to get from state $i$ to state $j$ (let the $n$-th state mean "there are still $n$ coins left"):

$$M_{i,j} = \begin{bmatrix} \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \\ 0 & \frac{1}{4} & \frac{2}{4} & \frac{1}{4} \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

and solve for 3 turns (that is you compute $M^3$) which answer is $$(M_{i,j})^3 = \begin{bmatrix} \frac{1}{512} & \frac{21}{512} & \frac{147}{512} & \color{red}{\frac{343}{512}} \\ 0 & \frac{1}{64} & \frac{14}{64} & \frac{49}{64} \\ 0 & 0 & \frac{1}{8} & \frac{7}{8} \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$$


Another related problem (for the interested) is to compute the expected number of turns.

To do this you can equate the expectations for the number of steps neccesary in the $x$-th state by means of the other $0$-th to $x$-th state.

E.g.

$$\begin{array}{} E[T_3] &=& \frac{1}{8} (E[T_3]+1) &+&\frac{3}{8} (E[T_2]+1) &+&\frac{3}{8} (E[T_1]+1) &+& \frac{1}{8} (1)\\ E[T_2] &=& &&\frac{1}{4} (E[T_2]+1) &+&\frac{2}{4} (E[T_1]+1) &+& \frac{1}{4} (1)\\ E[T_1] &=& &&&&\frac{1}{2} (E[T_1]+1)&+& \frac{1}{2} (1) \end{array}$$

Which can be solved as a problem with 3 linear equations and 3 unknowns.

This variant of your question is similar to the frog problem.

(I imagine that the simpler method by Henry to compute the probability to still be in the game after $n$ turns with $m$ coins as $P(turns>n) = 1-\left(1- {1}/{2^n} \right)^m$ allows an alternative computation of the expectation. And to do it without Wolfram Alphha you would have to split it up into different terms. $P(turns>n;m=3) = 8^{-n} - 3 \times 4^{-n} + 3 \times 2^{-n} $ where the sums of the individual terms can be solved as sums of geometric series )

$\endgroup$
6
$\begingroup$

You can split the problem into two (independent) parts so it becomes easier to solve.

Probability of flipping head for a coin after three attemps, the inverse of the probability of getting 3 tails in a row.

$1-(\frac{1}{2}*\frac{1}{2}*\frac{1}{2})= \frac{7}{8}$

Probability of flipping all three coins after three attemps, it is the same as the probability of flipping head for a coin after three attemps (i.e. using the probability calculated before) happening three times in a row :

$\frac{7}{8}*\frac{7}{8}*\frac{7}{8} = \frac{343}{512} $ ~= 67%

Final Result:

$\frac{343}{512}$

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Okay, I think I've figured out the answer. Funny how typing everything out tends to clarify some incorrect assumptions at the same time. I believe that my second methodology is actually correct, but that the individual probabilities that I assigned to each case were incorrect. For example, I had assigned the probability of flipping one "heads" and two "tails" on the first attempt to be (1/2 * 1/2 * 1/2 = 1/8), but I don't think that's correct in this case, because HTT is the same as THT and TTH. So the probability for that is actually 3/8, as is the inverse case of HTT, THT, TTH. A similar concept exists for HH vs HT vs TT. HT is also TH, so that has a probability of 1/2, while HH and TT retain their assigned probability of 1/4.

Given the above, the final formula is 1/8 + 3/16 + 3/32 + 3/32 + 3/128 + 1/512 + 3/128 + 3/256 + 1/64 = .57617

So you should expect that around 57.6% of the time you are able to get all heads in three attempts with three coins, without replacement.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think, that you can try to solve three identical, easier (one coin) problems, and then try to find out how to find the probability of the whole experiment together, as they are independent. $\endgroup$ – cure Oct 5 at 22:28
  • $\begingroup$ Your answer of $\frac{295}{512}$ is a little too low $\endgroup$ – Henry Oct 5 at 22:33
  • 2
    $\begingroup$ Your "final formula" is missing a 3/32. You have two but should have three, for "HHT,T,H" and "HTT,HH" and "HTT,HT,H" $\endgroup$ – Henry Oct 5 at 22:48
  • $\begingroup$ Agree, too low, a worksheet simulation of the game produces an average success of 0.67 based on the results of 16,000 games. $\endgroup$ – AJKOER Oct 6 at 1:01
  • $\begingroup$ Note, adding 3/32 to .57617 equals 0.6692 which agrees with my simulated success rate which I rounded to 0.67. $\endgroup$ – AJKOER Oct 6 at 1:10
1
$\begingroup$

You can think about it as trying to flip heads with one coin with three attempts.

  • After one attempt, the chance for H is 1/2.
  • After two attempts (that is, you get T, and then H), the chance is 1/4.
  • After three attempts (T, T, H), the chance is 1/8.

Add it all up and the chance that you win this minigame is 7/8. In reverse, you lose by flipping T, T, T, with probability 1/8.

As you have three coins, the actual game actually consists of three of these minigames, and you have to win all three of them to win the game. As the minigames are independent one another, you will have to calculate the probability of independent events, so the solution is just

$\left(\frac{7}{8}\right)^3 = \frac{343}{512}$, very close to $\frac{2}{3}$

You can extend this game to n coins and m attempts of flipping all heads, and the probability of winning the game will be:

$P_{n,m} = \left( \frac{2^m-1}{2^m} \right) ^ n$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

So there are 512 ways to get results when you toss 3 coins, that looks good. I think you're just missing a few nuances. It would help to the totals for each of the initial results (HHH, HHT, HTH, HTT, THH, THT, TTH, TTT) and make sure each one totals to 1/8th.

For example you have to results for an initial throw of HHT:

  • HHT, H = (1/16)
  • HHT, T, H = (1/32)

That only totals to 3/32 and it should be 4/32 or 1/8. You're missing the possibility that they throw HHT, T, T and never get all heads.

Also your HTT results (4 through 9) are missing something. I think for the second throw you are considering only 3 results, HH, HT, and TT. There's a fourth result though, TH.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Rather than calculating it as stopping flipping a coin once that coin comes up heads, you should calculate the probability based on flipping each coin three times first, and then looking at whether any of the results were heads.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Unless I am missing something, this is a very basic problem. You are throwing 1 coin 3 times and looking for the probability they will all come up heads, correct? This is dictated by the binomial distribution. But simply, p(heads) on toss 1 = 0.5. Probability that toss 1 and toss 2 come up heads = 0.5*0.5 = 0.250. Probability that toss 1, 2, and 3 all come up heads = 0.5 * 0.5 * 0.5 = 0.125.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Even simpler. There are eight possible outcomes (HHH, HHT, HTH, THH, HTT, THT, TTH, TTT)and only one does not contain a heads. If you stop after one or two throws makes no difference.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This answer suggests you are not reading the question in the same way everyone else is. $\endgroup$ – whuber Oct 8 at 15:20

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