19
$\begingroup$

I found this question and became curious, can anyone tell me the answer and prove it, i know it seems fairly simple but just thought an explanation of this would make an interesting case.

Flip a fair coin repeatedly until you get two heads in a row (HH assuming H indicates head and T indicates Tails). On average, how many flips should this take? What if we flip until we get heads followed by tails (HT)? Are the answers the same?

$\endgroup$
  • 2
    $\begingroup$ The answers so far aren't quite correct... it's a little bit more complicated than what they're saying. Here's an equivalent question on Math.SE: math.stackexchange.com/questions/364038/… $\endgroup$ – TheRubberDuck Oct 22 '14 at 13:03
  • 1
    $\begingroup$ I'm not sure I understand and believe those answers well enough to turn it into something more appropriate for puzzling. If I do before a better answer is posted, I'll post one. $\endgroup$ – TheRubberDuck Oct 22 '14 at 13:12
  • 1
    $\begingroup$ There's a cool technique I learnt called a tree diagram. You use it in statistics to find the probability of something, here's a link to help explain in detail :) statistics.about.com/od/ProbHelpandTutorials/ss/… $\endgroup$ – SomeAmbigiousUserName Oct 22 '14 at 14:22
  • 1
    $\begingroup$ I've enjoyed this because the answer isn't at all what I expected. $\endgroup$ – Octopus Oct 22 '14 at 23:30
  • 1
    $\begingroup$ @TreyTaylor, you may enjoy Markov Chains even more. If I get some time this evening I'll put up an answer involving those. en.wikipedia.org/wiki/Markov_chain $\endgroup$ – ymbirtt Oct 23 '14 at 13:13
23
$\begingroup$

Case 1: Waiting for HH

$A$ = average nb. of flips to get HH after T or nothing.
$B$ = average nb. of flips to get HH after H.

A is 1 flip, plus B if you get H and continue, or plus A if you get T and restart:
$A = 1 + {1\over2}B + {1\over2}A$

B is 1 flip, and you are done if you get H, or plus A if you get T and restart:
$B = 1 + {1\over2}0 + {1\over2}A$

This resolves to

$B = 1 + {1\over 2}A$
$A = 1 + {1\over 2} (1 + {1\over 2} A) + {1\over2} A$
$A = 1 + {1\over 2} + {1\over 4} A + {1\over 2} A$
$A = 6$

The expected number of flips to get HH is 6.

Case 2: Waiting for HT

$A$ = average nb. of flips to get HT after T or nothing.
$B$ = average nb. of flips to get HT after H.

A is 1 flip, plus B if you get H and continue, or plus A if you get T and restart:
$A = 1 + {1\over2}B + {1\over2}A$

B is 1 flip, and you are done if you get T, or plus B if you get H and wait for T again:
$B = 1 + {1\over 2}0 + {1\over 2}B$

This resolves to:
$B = 1 + {1\over 2}B$
$B = 2$
$A = 1 + {1\over 2}2 + {1\over 2}A = 2 + {1\over 2}A$
$A = 4$

The expected number of flips to get HT is 4.

Comparison

The difference comes from the fact that in the first case, if you get the wrong 2nd result, you start all over, while in the second case you continue with one good result.

$\endgroup$
  • 1
    $\begingroup$ :) it seems so simple, but @Florian F that was a great answer $\endgroup$ – skv Oct 22 '14 at 13:22
  • $\begingroup$ Already accepted? That was fast! $\endgroup$ – Florian F Oct 22 '14 at 13:22
  • $\begingroup$ I'm getting a different result for $\text{HT}$; $5$ instead of $4$. Would you care looking at my answer? $\endgroup$ – SQB Oct 22 '14 at 14:27
5
$\begingroup$

To supplement Florian's answer and perhaps help make it more clear why it is correct that HH requires more expected coin tosses than HT, look at a list of all possible outcomes of three coin tosses:

HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

Now look at when we get HH or HT:

HHH      HH after 2
HHT      HH after 2, HT after 3
HTH      HT after 2
HTT      HT after 2
THH      HH after 3
THT      HT after 3
TTH
TTT

Even at this point HT is showing up more frequently - we have 1/4 chance of getting HH or HT after 2 (as you probably expected), but overall we have a 1 in 2 chance of getting HT compared to a 3 in 8 chance of getting HH within three coin tosses.

For HH, here are the combos that don't work:

HTH
HTT
THT
TTH
TTT

Of these, two ended with heads and might only require one additional coin toss to win. For HT:

HHH
THH
TTH
TTT

Three of the four end with heads and might only require one additional coin toss to win.

So after three coin tosses, you're more likely to get HT than HH, and you're also more likely to be in a position where the next coin toss might be a success! (3 in 4 chance over a 2 in 5 chance).

$\endgroup$
  • $\begingroup$ You miscounted. In that second block the first example HHH has HH after 2 AND AFTER 3! That makes the occurances of HT and HH exactly equal. You have HH twice at position 2, twice at position 3 and also HT twice at position2 and twice at position3. Ha! Still looks like even odds to me! $\endgroup$ – Octopus Oct 22 '14 at 23:27
  • 3
    $\begingroup$ @Octopus it can't double count - you would have stopped after the second toss. $\endgroup$ – Rob Watts Oct 23 '14 at 4:34
5
$\begingroup$

HH

Following the method outlined in this answer on Math.SE, we get the following:

Let $e$ be the expected number of tosses.

Start tossing. If we get a tail immediately (probability $\tfrac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\tfrac{1}{4}$), then the expected number is $e+2$. Finally, if our first $2$ tosses are heads (again with probability $\tfrac{1}{4}$), then the expected number is $2$. Thus $$e=\frac{1}{2}\cdot(e+1)+\frac{1}{4}\cdot(e+2)+\frac{1}{4}\cdot(2)$$ Solving this for $e$ yields $e=6$.

HT

Again, let $e$ be the expected number of tosses and start tossing.

If we get a tail immediately (probability $\tfrac{1}{2}$) then the expected number is $e+1$. If we get a head followed by another head (probability $\tfrac{1}{4}$), then the expected number is $e$, since only the first head can't be part of the sequence and were already $1$ deep into the sequence. Finally, if our first $2$ tosses are exactly heads followed by tails (again with probability $\tfrac{1}{4}$), then the expected number is $2$. Thus $$e=\frac{1}{2}\cdot(e+1)+\frac{1}{4}\cdot(e)+\frac{1}{4}\cdot(2)$$ Solving this for $e$ yields $e=4$.

$\endgroup$
  • $\begingroup$ This doesn't quite work because when you get two heads you're not back to the original state, so you can't use $e$ to express the expected number of tosses from that point. $\endgroup$ – Rob Watts Oct 22 '14 at 14:24
  • 1
    $\begingroup$ It should be 4. You need 2 tosses on average to get an H, then 2 more tosses to get a T. $\endgroup$ – Florian F Oct 22 '14 at 15:52
  • $\begingroup$ @FlorianF By that logic, HH should be 4 as well. $\endgroup$ – SQB Oct 22 '14 at 16:15
  • 1
    $\begingroup$ @RobWatts Thank you, you pointed me in the right direction. $\endgroup$ – SQB Oct 22 '14 at 16:24
  • $\begingroup$ +1 This is a very nice approach because it needs only the very basic about probabilistic theory. $\endgroup$ – yo' Oct 23 '14 at 11:32
4
$\begingroup$

Not exactly proof, but this short Python program simulates the problem:

Case HH or 0,0 from the random numbers 0,1

import random

accum = 0.0
count = 0.0

while count<10000:
  seq = []
  while True:
    n = random.randint(0,1)
    seq.append(n)
    if len(seq)>=2 and seq[-2]==0 and seq[-1]==0:
      break
  #print seq
  accum += len(seq)
  count += 1

print accum/count  

Case HT or 0,1 from the random numbers 0,1

import random

accum = 0.0
count = 0.0

while count<10000:
  seq = []
  while True:
    n = random.randint(0,1)
    seq.append(n)
    if len(seq)>=2 and seq[-2]==0 and seq[-1]==1:
      break
  #print seq
  accum += len(seq)
  count += 1

print accum/count  

Generates a number close to 6 for HH and a number close to 4 for HT, which seems to support the answer provided by Florain F and others.

That does not go with my intuition which told me the answers should be similar

$\endgroup$
1
$\begingroup$

Previous answers have stated that the probability of getting either a HH or HT combination is 1/4. Based on that, we expect that it would take 1/p or 1/(1/4) tries to achieve it. Therefore, I would say that it would take 8 flips (4 * 2 flips).

Edit: Well, it seems my reasoning is flawed, but there is hope from https://math.stackexchange.com/questions/364038/expected-number-of-coin-tosses-to-get-five-consecutive-heads

Based on that, we get e = 1/2 * (e+1) + 1/4 * (e+2) + 1/4 * 2 which works out to

e = 6, so 6 tries for HH

Edit again: I thought the answers were the same, but it looks like they are different. The second equation is only 1/2 * (e+1) + 1/2 * 2, which works out to

e = 3, so 3 tries for HT

So, ultimately, the probabilities are different.

$\endgroup$
  • $\begingroup$ the question is not about the number alone, can you read the final question and edit accordingly :) $\endgroup$ – skv Oct 22 '14 at 13:18

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.