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 break-even 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ⁿ-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 n-m entries of the target sequence. Their winnings will be 2^_(n-m) - 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 n-m entries of the target sequence. Their winnings will be 2^_(n-m) - 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⁷-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.