Solved – Probability of flipping heads after three attempts

probabilityself-study

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:

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.
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.

Best Answer

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$

Related Solutions

Solved – How to evaluate quality of probability estimator for Bernoulli experiments

You can quantify the quality of the estimator by calculating the total surprisal of all of the coin flips.

Suppose that your expert makes predictions $q_i$ for each coin. Then, given indicator variables for the coins coming up heads $x_i$, the total surprisal is:

\begin{align} \sum_i\left[ -x_i\log q_i - (1-x_i)\log (1-q_i)\right]. \end{align}

The expected value of the surprisal given the true values $\{p_i\}$ is the cross-entropy: \begin{align} \sum_i \left[-p_i\log q_i -(1-p_i)\log (1-q_i)\right]. \end{align} It is nonnegative, and achieves its minimum value (the entropy of $\{p_i\}$) if and only if $p_i = q_i \forall i$.

If you subtract the entropy from the cross-entropy, you get the relative entropy (whose minimum value is zero). If you take $e^{-x}$ of that, you have a number in $[0, 1]$ as you wanted with a reasonable probabilistic interpretation.

Solved – Does the probability of multiple independent events follow a normal distribution

One simple way to think about probabilities is to enumerate all the possibilities and weight them according to their likelihoods, and then you can just count the number of different combinations. (This approach will work when the events are discrete and few in number.)

Let's start with a fair 4-sided die (you'll see the reason for this odd choice soon) and a fair coin. By "fair", I mean that all the possible outcomes are equally likely. That is, the likelihood of getting a 1 is exactly the same as getting a 4, for example, and that the likelihood of getting heads is exactly the same as getting tails. As @MichaelChernick points out, if you were to flip the coin 4 times and count the number of heads, you would find there are 5 possible final counts, so we will equalize the ranges by flipping the coin only 3 times, and subtracting 1 from the result of the die roll. Thus, both will range from 0 to 3. Now we can lay out the possibilities.

For the die:

{0, 1, 2, 3}

All of which are equally likely, because we've stipulated the die is fair, and so each possible event has a probability of 1/4.

For the coin, it's more complicated. Each individual flip is {H, T}, but we ultimately want to know about the combination of 3 different flips, so we need to lay out the combinatorics and then count the resulting number of heads.

                 flip    
possibility     1  2  3     number of heads
     1:        {H, H, H,           3
     2:         H, H, T,           2
     3:         H, T, H,           2
     4:         H, T, T,           1
     5:         T, H, H,           2
     6:         T, H, T,           1
     7:         T, T, H,           1
     8:         T, T, T}           0

We see here that the number of possibilities grows exponentially with each additional flip. Specifically, it doubles, because there are two possible outcomes of each flip; if we were flipping a 3-sided coin (assuming one could exist) it would triple. If we had thrown a 6-sided die and flipped the coin 5 times, it would have taken 32 lines to lay out all the possible combinations of outcomes. In our case, with three flips, it took $2^3=8$ lines to lay out all of the possibilities.

Now (again) because we stipulated that heads and tails are equally likely, and because we have laid out all the combinations, each possibility is equally likely, having a probability of 1/8. But note that this does not mean that each possible number of heads is equally likely. There are three different ways to end up getting 1 head, and three ways to end up with 2 heads, but only 1 way each of getting 0 or 3 heads. Thus, the probability of getting 0 heads is 1/8, of getting 1 head is 3/8, of getting 2 heads is 3/8, and of getting 3 heads is 1/8. In general, the probability of getting the number of "successes" $k$ (i.e., heads in our case) out of the number of "trials" $n$ (flips), where each trial has a probability of success $p$, will be: $$ p(k)=\frac{n!}{k!(n-k)!}p^k(1-p)^{n-k} $$ As a result of this, "the coin tosses sort of lump in the middle", as you suspect, and as you can clearly see:
enter image description here
These distributions do have things in common (which I think is what is confusing you): they are both discrete, have the same number of possible results (at least under our modified arrangement), and have the same average (more technically expected value). However, as their Wikipedia pages state, they differ in their higher moments; namely their variances (uniform: $(n^2-1)/12$ vs. binomial: $np(1-p)$ ) and kurtoses (uniform: $-(6n^2+6)/(5n^2-5)$ vs. binomial: $(1-6p+6p^2)/(np(1-p))$ ) differ.

On a slightly different note, the title of the question asks about how the distribution of coin flips will compare to the normal distribution, while the body of the question asks about how it compares to a discrete uniform. My answer here has mostly focused on the body of the question, but I should mention that the binomial is sometimes colloquially referred to as the "discrete normal" distribution. One way to think about this is that as the number of coin flips continues on towards infinity, it's binomial distribution will converge to the (continuous) normal distribution.

Best Answer

Related Solutions

Solved – How to evaluate quality of probability estimator for Bernoulli experiments

Solved – Does the probability of multiple independent events follow a normal distribution

Related Question