Which sequence will occur
first?
Try out (or imagine) the
following simple game with a friend:
You each toss a fair
coin as many times as necessary to get a
required sequence.
Your required sequence is H T H
Your friend's
required sequence is H T T.
Do this several times and each time write down the number of tosses you needed
The winner is the player whose average number of tosses is the lowest. For example:
Game
1:
You toss: H H T H T H
Friend tosses: H T H H H
T H H T T
Your 'score'
is 6 and your friend's is 10
Game
2:
You toss: T T H T
T H H T H
Friend tosses: T T H H T
H
T T
Your
'score' is 9 and your friend's is 8
Game
3:
You toss: T
T H H T H
Friend tosses: H H T H T T
You both 'score' 6.
At this point your average is 7 and your friend's average is 8.
The conundrum: Assuming you played the game many times, which of the following
outcomes would you expect?
A) You
win (i.e. your average is lower than your friend's).
B) Your friend
wins (your average is higher than your friend's).
C) You tie (your average is about the same)
If you answered C then
the good news is that you agreed with most people including
leading intellectuals
and even mathematicians. But the bad news is you are wrong.
It
turns out that the correct answer is B. The average
number of tosses required to reach the H T T sequence is 8
compared to an average of 10 that are required for the
sequence H
T H.
Why is this?. First I
can give a purely intuitive explanation of why this might be the
case. Both you and your friend need to toss the sequence H T
immediately before reaching your required sequence. So suppose that has
happened. Then at that point you both have a 50% chance of
reaching the target on the next toss. But suppose you both lose. That
means your most recent sequence is H T T and your friend's most
recent sequence is H T H. So, whereas your friend is now at least TWO
throws away from winning, you are at least THREE throws away from winning.
There is actually a
simple way to calculate the average number of throws required to get
any particular sequence of H's and T's. It is based on the idea of a
fair casino. The explanation is here.
And if you thought that was counterintuitive...
...then this is going to really freak you out. Asking the question we did above, namely
Which of two sequences will on average require fewer tosses to achieve?
is different from the following question:
What is the probability that one sequence will occur before the other.
Although different it seems intuitively obvious that the sequence that
requires fewer tosses on average is also the one with the greater
probability of occuring first. In fact this is not always true.
For example, consider the two sequences THTH and HTHH.
It turns out that the average time needed to achieve THTH is 20 and the average time needed to achieve HTHH is 18 (you can work this out for yourself by following the method explained here).
But, incredibly, the probability that
THTH occurs before HTHH is 9/14 compared with a probability of just 5/14 that HTHH occurs before THTH. And there are many other such examples.
Calculating the average
number of throws required before getting a particular sequence
Let's imagine a
completely 'fair' casino, meaning that no matter what game is played,
the average amount that is paid out in winnings should equal the amount
bet. So, as a very simple example, one game played in the
casino is "tossing a coin" where you simply bet on a particular outcome
H or T. If you bet a chip on H then you win a chip (and get your bet
returned) if H comes up. Otherwise you lose the chip you bet.
Assuming the coin is fair (meaning H comes up 50% of the
time) the game is fair since the average amount that is paid out
in winnings should equal the amount bet. Another example of a
fair game would be a roulette wheel with just 36 numbers (1 through to
36) in which you bet a chip on a single number and if it comes up you
win 36 chips. A roulette wheel with a 0 (as in real casinos)
is not fair because your actual probability of winning is 1/37 not
1/36. To be fair the payout on a win should be 37 chips not
36. The difference is enough to ensure that, over time, the
casino wins more than is bet.
Now consider a game in a fair casino where the gamblers bet on a
particular sequence of coin tosses, namely the sequence H T H.
The betting rules are as follows:
 Each time
the coin is tossed one new gambler bets a single chip until the sequence H T H is
achieved.
 As long as a
gambler can still win his stake and winnings go back in the
game
(hence doubling until either he wins or the game ends.
To make this clear here
is an example game.
Sequence actually thrown: H H T
T H T H
The
following table shows the sequence of bets. The final column shows the
amount won by each gambler

H

H

T

T

H

T

H


Gambler
1

Bet
1

Lost






1

Gambler
2


Bet
1

Lost





1

Gambler
3



Bet
1 Lost





1

Gambler
4




Bet
1 Lost




1

Gambler
5





Bet
1

Win

Win

7

Gambler
6






Bet
1 lost


1

Gambler
7







Bet
1 win

1

Thus:
Throw 1:
Gambler 1 bets one chip. Stays in the game as H is first part
of required sequence H T H
Throw 2:
Gambler 2 bets one chip. Stays in the game as H is first part
of required sequence H T H
Gambler 1 loses because he has now got the losing sequence H H
Throw 3:
Gambler 3 bets one chip, loses as he has losing sequence
T
etc.
Note that Gambler 5 is the one who bets on the winning sequence. He
wins 7 chips plus his stake (since on throw 6 he puts in 2
chips and in throw 7 he puts in 4 chips). But Gambler 7 also wins a
chip.
Now imagine any other possible sequence in which the first occurence of
H T H is at the end. For any such sequence there will be just one
gambler who wins 7 chips (the one who entered the game three throws
from the end) and one gambler who wins 1 chip (the one who entered on
the last throw). So, no matter how many throws are
required to win the game the casino will always pay out 8 chips. In the
above example the casino loses overall because it only recovers 5 chips
from the 5 losing players. But if the game required, say 13 throws to
achieve the winning sequence, then there would be 11 losing
players, so the casino wins 3 chips overall.
Since the game and the casino are 'fair' it must be the case that on
average the money paid out to winners should be equal to the money won
from losers. That means that, on average, the game should involve 10
tosses because that is the only number for which the net payout (8
chips) is equal to the net income (8 chips).
Hence,
the average number of tosses before achieving the sequence H T H must
be 10.
Now consider the sequence H T T. No matter how many throws of
the coin are needed there will this time be just one winner  the
gambler who entered
the game three throws from the end. The two gamblers who follow both
get a T on their first throw and so lose. This means that the casino
always pays out 7 chips in winnings. So, it needs 7 'losers' to break
even. Together with the one winner this makes 8 players in total, so
the breakeven point is 8 throws. Again, given that it is 'fair' the average number of throws
before achieving the sequence H T T must be 8.
You can use this same approach to work out the average number of throws
required to achieve any sequence of H's and T's as follows:

Note that, if the sequence (which we will call the target sequence) is length n then any gambler who entered the
game more than n throws from the sequence being achieved must lose.

The gambler who entered the game n throws from the end is the 'winner'
and will win 2^{n}1 chips.
 Any gambler who entered the game m throws from the end where m>n will win providing that their sequence matches the first nm entries of the target sequence. Their winnings will be 2^{(nm)}  1 chips.
 So, in general any gambler who entered the game m throws from the end where m>=n will win providing that their sequence matches the first nm entries of the target sequence. Their winnings will be 2^{(nm)}  1 chips.
 So, for the total paid out by
the casino to be equal to the total lost by gamblers, the number of
losing gamblers must be equal to the sum of the total chips paid to
winners. Hence the average number of throws is this number plus
the number of winners.
Example
Suppose the target sequence is H T H H H T H
Then the sequence is length 7 so the winner is the gambler who entered 7 throws before the target is reached. He wins 2^{7}1 chips, that is 127.
But in addition the gambler who entered 3 from the end wins 7 chips
(due to the sequence H T H also being the start of the target sequence)
and the gambler who entered on the last throw wins 1 chip (because H is
the start of the target sequence). The total paid out is
therefore 135. Since there are 3 winners, the average number of throws
required to meet the target is 138.