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?
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.
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).
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$.
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$.
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
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.
