A Coin-Flipping Problem

One problem that I’ve assigned when discussing Markov chains is to calculate the expected number of flips required for a particular pattern to appear.  (Here I mean a pattern such as heads, heads, heads, or HHH.)  In this post I’m going to discuss another approach – one that doesn’t use Markov chains – to solve this problem.

Suppose we want to find the expected number of flips required for the pattern HHH to appear.  Call this X.  We can calculate X by conditioning on the various patterns we might achieve that do or don’t give us HHH.  For example, for our first few flips we could observe T, HT, HHT, or HHH.  These cover the entire outcome space and have probability 1/2, 1/4, 1/8, and 1/8, respectively.

  • If we observe T, then we effectively have to start the entire process over, and we’ve used one flip to get to that point.  So, if we observe T, then the average number of flips required is 1+X.
  • If we observe HT, then we also have to start the entire process over, and we’ve used two flips to get there.  For this outcome, the average number of flips required is 2+X.
  • If we observe HHT, then we have to start the entire process over, and we’ve used three flips.  The average number of flips required for this scenario is 3+X.
  • Finally, if we observe HHH, then we have achieved our goal.  The number of flips required is 3.

All together, then, the average number of flips required satisfies the equation

\displaystyle X = 1/2(1+X) + 1/4(2+X) + 1/8(3+X) + 1/8(3).

Solving for X, we obtain X = 14.  So it takes 14 flips, on average, to obtain three consecutive heads.


What if we have a more complicated pattern, though?  Let’s look at HHT as an example.  Let X be the expected number of flips required for HHT to appear for the first time.

Once again, we can condition on the various patterns we might achieve that do or don’t give us HHT.  These are T, HT, HHH, and HHT.  As in the previous example, these cover the entire outcome space and have probability 1/2, 1/4, 1/8, and 1/8, respectively.

  • If we observe T, then we have to start over.  The average number of flips required is 1+X.
  • If we observe HT, then we have to start over.  The average number of flips required is 2+X.
  • If we observe HHH, then we don’t have to start over.  It’s entirely possible that the HH at the end of HHH could be followed by a T, and then we would have achieved our pattern!  Mathematically, this means that things get a bit more complicated.
    • Let E_{HH} denote the expected number of flips required for HHT to appear given that we currently have HH.
    • Thus if we start with HHH, then the average number of flips required to obtain HHT is 3 + E_{HH}.
    • Now we need to determine E_{HH}.
      • If we currently have HH, then the next flip is either a T, which completes our pattern, or an H, we means we must start over in our quest to complete HHT given that we currently have HH.
      • Thus E_{HH} = 1/2(1) + 1/2(1 + E_{HH}).
      • Solving this yields E_{HH} = 2.
    • Thus if we observe HHH, then the average number of flips required to obtain HHT is 3 + 2 = 5.
  • Finally, if we observe HHT, then we have achieved our goal in 3 flips.

Therefore, X = 1/2(1 + X) + 1/4(2 + X) + 1/8(5) + 1/8(3).  Solving this equation for X gives us X = 8 flips.

Notice that it takes fewer flips, on average, to achieve HHT than it does HHH.  This is because we don’t always have to start over every time the sequence fails to mach our goal sequence.

The interested reader is invited to find the expected number of flips for the other sequences.

 

This entry was posted in coin flipping, Markov chains, probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s