Maths - behind the scenes / Puzzles / Stats

Hedgehog versus Raccoon

Do you know this Sunday evening feeling: you planned to do so much work this weekend, you miserably failed, but you’re exhausted anyway? Well, you definitely do if you’re a PhD student. My body and mind are too tired for any activity other than coin flipping. I specialise in probability and stats in the end!

Actually no, I’m too tired to even throw the coin myself. I’ll watch my special assistants, the shy Hedgehog and the keen Raccoon playing a game. The rules are easy: each of them flips a fair coin, Hedgehog wins when the first sequence HH appears, while Raccoon is waiting for HT (H stands for heads, T for tails).


Raccoon and Hedgehog flipping a coin.

The game should be fair, as the probability of getting HH in two coin flips is ¼, the same goes for HT. Why? Coin flips are independent, which means that the result of a coin flip doesn’t depend on previous flips. Thus the chance of getting H in the first flip is ½, in the second flip – also ½. As the same concerns tails, both HH and HT are equally likely to occur in two coin flips.

Unfortunately our poor Hedgehog keeps losing. If the game really was fair, we’d expect both players to win more or less half of the time. She gets upset and asks me, the mathematician, to explain what’s happening.

We want to estimate how long, on average, both players should wait for their sequence.  Let’s draw some pictures to see what’s happening. Disclaimer: I almost failed my art classes. Plus I’m tired. Plus Picasso wasn’t successful in the beginning either.


How do we get HH?


How do we get HT?


The pictures present possible ways of getting HH (top) or HT (bottom). H and T represent the current state, so the last coin flip. Each arrow shows the transition, for example an arrow between H and T means that we flipped H and than T.  Notice that from each state we draw two arrows, because we have a 50:50 chance of getting a tail or a head in each coin flip. Since each arrow corresponds to one coin flip, with each transition we add one to the expected number of flips before getting the desired sequence. I marked the “good” transitions (so the transitions that make us closer to our final sequence) with green, while the “bad” ones with red.

Are you with me so far?

Look at these two pictures. They aren’t the same! This is the first indication that the game might not be as fair as we thought. In the left picture you can see that if our Hedgehog is in the state H, she either flips H and wins or flips T and has to start from scratch. On the other hand, the right picture shows that when Raccoon is in the state H, he either flips T and wins or flips H and is still half-way through his sequence. What a sneaky Raccoon!

Now we understand intuitively why Hedgehog is upset. If it’s enough for you, skip the rest of the post (and have a good night!). If you’d like to know how long both players should expect to wait for their sequence, let’s compute together the expected value of coin flips before reaching each sequence.

A while ago I already explained what we mean by expected value, check out this post if you need a refresher. Let’s start with Hedgehog. I’ll denote by E[N] the expected number of flips before reaching HH. You can follow all the steps in the diagrams.

If in the first flip we get T, we don’t get any closer to our goal, so we have to wait E[N] more flips. If the first flip gives us H, we have 50:50 chance for these possibilities:

  • we flip H again and win in 2 flips;
  • we flip T and are back to the beginning, so we have to wait E[N] more flips.

Since all these events happen with probability ½, we’re left with the equation: E[N]=½*(E[N]+1)+½*(½*2+½*(E[N]+2)). One equation, one unknown, so we solve it and get E[N]=6.

Now let’s see what our Raccoon is up to. Let E[M] be the expected number of flips before reaching HT and E[H] – expected number of flips before getting a head, no matter where we start. Again, pictures might be helpful.

Let’s compute E[H]. With equal odds:

  • we get H in 1 flip;
  • we flip T and have to wait E[H] more flips.

We need to solve a simple equation: E[H]=½*1+½*(E[H]+1), which gives us E[H]=2.

Now let’s take a look at the whole game. As before, getting T in the first flip doesn’t get us anywhere, so the first term in the right-hand side of the equation stays the same. What happens if we first get H? Now we need to wait E[H]=2 flips. So our final equation is we’re left with the equation E[M]=½*(E[M]+1)+½*(E[H]+1), which gives us the answer E[M]=4.

It means that on average Raccoon has to flip the coin 4 times to win, while Hedgehog needs to wait 6 turns. Not fair at all!

Oh, and by the way: maybe money doesn’t bring happiness, but coin flipping definitely does!







Leave a Reply

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

You are commenting using your 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