Intro: This article was written after the swindle it describes was discussed in Bob Farmer's monthly column in MAGIC magazine.

The Con: Hustler and mark each pick a sequence of Heads and Tails of length 3, i.e. one of HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. They then start flipping a coin, keeping track of the three most recent tosses, in order. The person whose sequence comes up first wins.

The Secret: The mark always picks first. Whatever sequence the mark picks, the hustler can pick another sequence that is likely to come up first. The rule by which the hustler operates is

	1.  Take the 1st and 2nd elements of the mark's sequence.
	2.  Add the opposite of the 2nd element of the mark's sequence to the
	    beginning of the two elements already chosen.

The Discussion: This is an excellent example of a phenomenon known as non-transitive probabilities. This is well-known to statisticians and pollsters who have often seen electoral contests between three candidates A, B, and C where it is established that if only A and B were running, A would win, and if only B and C were running, B would win, but if only C and A were running, C would win.

The Details: To simplify the writing task, we shall refer to each sequence by a number according to the following table:

	HHH		0
	HHT		1
	HTH		2
	HTT		3
	THH		4
	THT		5
	TTH		6
	TTT		7

The numbering could be done in any order - here we have simply interpreted H as 0 and T as 1, then taken the binary interpretation of each sequence. From this point, we shall refer to sequences only by number.

Each sequence can be followed by exactly two others. In the case of sequence 0 and sequence 7, one of the two possible following sequences is the same as the current sequence. In all cases, the two possible following sequences are equally likely, since the coin is assumed to be balanced. This is represented diagramatically in the figure below.

Note that in this diagram the connecting lines are arrows. These indicate which sequences can follow which. It is not important to our discussion which edges correspond to "H" and which to "T", but the interested reader may wish to determine the edge-labels.

This graph, as it happens, is a very famous one - it is called the de Bruijn Graph of order 3 (pronounced de-broyn) in honour of the Dutch mathematician who first described it. It has numerous interesting properties and is frequently discussed in the context of parallel algorithms and communications networks.

Playing the game is exactly equivalent to randomly picking a starting point in this graph (representing the first three coin tosses) and then randomly following arrows until one of the two chosen sequences is reached. To determine the probability of each of the two players winning, we simply analyse all of the possible random walks through the graph from all possible starting points. This is not as daunting a task as it might seem.

Suppose A and B are the two chosen sequences. We will explicitly compute the probability that the player choosing A wins the game - the probability that the other player will win is of course just 1 minus the value we will compute.

There are 8 possible starting points in the graph. Let x be any starting point. We shall use f(x) to represent the probability that A wins if the game starts at x.

Clearly f(A) = 1 ; if the first three tosses form the sequence A, the player wins automatically. Similarly, f(B) = 0, since this means the first three tosses formed the other player's sequence.

In general, if point x is followed by points y and z then

	f(x) = 0.5*f(y) + 0.5*f(z)

This is because both successors are equally likely, and because the process of tossing the coin is memoryless. That is, if the first sequence formed is neither A nor B, then it is just as if the very first toss never happened, and the second sequence formed effectively becomes the first one we should consider.

Thus we can write down 8 equations of the form f(x) = ... , one for each of the 8 starting points. Solving these gives the exact probability that A will win in each case. Summing them all and dividing by 8 (all starting points are equally likely, so we simply average them) we arrive at the probability that A will be reached before B.

An example: Let A = 1 and let B = 3. Here are the equations :

f(0) = f(1)			- this is because 0 is not a winner or loser, and 
				  the only other sequence that can follow 0 is 1
f(1) = 1			- that is, A comes up immediately and the 
				  player wins
f(2) = 0.5*f(4) + 0.5*f(5)	- 2 is neither a winner nor loser - it leads 
				  to sequences 4 and 5 with equal probability
f(3) = 0			- the other player's sequence comes up 
				  immediately - our hero loses
f(4) = 0.5*f(0) + 0.5*f(1)	- as for 2
f(5) = 0.5*f(2) + 0.5*f(3)	- as for 2
f(6) = f(2)			- point 2 and point 6 have exactly the same 
				  successors in the graph - thus they have the 
				  same probability of leading to a win
f(7) = f(6)			- as for 0

Immediate simplification gives

f(0) = 1
f(1) = 1
f(2) = 0.5 + 0.5*f(5)
f(3) = 0
f(4) = 1
f(5) = 0.5*f(2)
f(6) = f(2)
f(7) = f(2)

Substituting f(5) into the formula for f(2), we get

f(2) = 0.5 + 0.25*f(2) 

0.75*f(2) = 0.5    

f(2) = 2/3

Thus we end with

f(0) = 1
f(1) = 1
f(2) = 2/3
f(3) = 0
f(4) = 1
f(5) = 1/3
f(6) = 2/3
f(7) = 2/3

Summing and dividing by 8 we find that sequence 1 wins with probability 2/3. Therefore sequence 3 wins with probability 1/3. We conclude that the odds are 2:1 in favour of sequence 1. This analysis becomes much easier after it is done once or twice. Patterns such as f(4) = f(0) = f(1) and f(3) = f(7) = f(6) are frequently apparent.

We could apply this process to compute the odds for each of the 28 possible pairs of chosen sequences. Fortunately the game is full of symmetries and the number is greatly reduced thereby. For example, the relationship between sequences 0 and 5 is exactly the same as that between sequences 7 and 2, as can be seen from the diagram. It turns out that we only need compute the odds for 12 pairs. Doing so and applying the symmetries to complete the table, we construct the following table of odds

	0	1	2	3	4	5	6	7

0	-	1:1	2:3	2:3	1:7	5:7	3:7	1:1

1		-	2:1	2:1	1:3	5:3	1:1	7:3

2			-	1:1	1:1	1:1	3:5	7:5

3				-	1:1	1:1	3:1	7:1

4					-	1:1	1:2	3:2

5						-	1:2	3:2

6							-	1:1

7								-	

As an example of how to apply the table, suppose the mark chooses sequence 2. Examining the odds of all other sequences against sequence 2, we find that sequence 1 fares the best with odds of 2:1. Thus the hustler chooses sequence 1 to play in this instance. As it turns out, in each case the best choice is one of the two immediate predecessors in the diagram of the sequence chosen by the mark. This makes sense in that the hustler should choose a sequence that lies on as many as possible of the random paths leading to the mark's sequence, and it explains why the 'rule' makes the last two elements of the hustler's sequence equal to the first two elements of the mark's choice.

It is possible to simplify the game to sequences of length 2, or to enlarge it to sequences of length 4 or more. The same analysis can be applied to determine which sequence the hustler should pick - though with sequences of just 2 tosses, the hustler is not always able to tip the odds in his or her favour.

.

The 3rd order de Bruijn graph

About the Author