I recently stumbled across some YouTube videos about Penney’s game. Here is one of them. The problem was actually new to me, like almost all problems in mathematics. There simply are too many. It is easier to come up with a problem than a a solution.
According to Wikipedia, Walter Penney published the problem in the Journal of Recreational Mathematics in 1969. The article seems to be hard to get, so simply let us start an analysis ourselves. After all, that sounds like a lot of fun, and I have written about a similar problem in this blog before.
Assume we toss coins with outcome 0 and 1 at equal probability. So we get a sequence of tosses like
\(0,1,0,0,1,1,1,0,1,0,\ldots\)
We are studying the following game between two players:
- Player A selects a triplet of tosses (like 0,0,1), and player B another triplet (like 1,0,0).
- The player whose triplet appears first in the sequence of tosses wins.
Given the sequence above and the selected examples of triplets above, player B would win. His triplet 1,0,0 appeared immediately after four tosses.
If both players select their triplet secretly this is obviously a fair game.
There is a counterintuitive fact here: It is an illusion that the choice of the triplet matters. The average waiting time for any triplet is equal, and selecting (1,0,1) is no better than (1,1,1).
To understand this, we need to see the tossing as a sequence of triplets. In the example above the sequence is the following:
\((0,1,0) \to (1,0,0) \to (0,0,1) \to (0,1,1) \to (1,1,1) \to \ldots\)
All triplets have the same chance (namely 1/8) to appear at the start of the sequence. And any triplet T has exactly two other triplets S1, S2 which can lead to this triplet. Since S1 and S2 have the same chance (namely 1/8) to appear in the n-th position of the sequence and T is selected with probability 1/2 from each, the chance for T to appear in the (n+1)-th position is also 1/8.
After this first excursion into the mathematics of random walks, we need to come back to the third rule of Penney’s Game.
- The player B selects his triplet after seeing the selected triplet of player A.
Now, there is no reason why player B shouldn’t have an advantage. After all he can simply take the same triplet and get a draw. If he was forced to take another triplet he might even be at a disadvantage. But, indeed, he has a big advantage of at least 2:1. A wrong selection of player A can make his chances even worse.
Let us try to understand this. This is a case of non-transitive ordering.
- Let us write S>T if the triplet S is more likely to appear before triplet T in the toss sequence when the tosses are started with a random triplet.
Then it is not true that
\(T \ge S \,{\rm and}\, S \ge U \Longrightarrow T \ge U\)
If it were true, the ordering would be complete and player A could select the best triplet, or at least a triplet that cannot be beaten by the selection of player B.
It turns out that for each selected triplet T of player A, there is a selection S which is better than T (S>T). This makes the game a win for player B.
This is counterintuitive again. A consequence is that there is a sequence of triplets with the property
\(T_1 < T_2, \quad T_2 < T_3, \ldots \quad , T_{n-1}<T_n, \quad T_n < T_1\)
In this game, the simple rule to find a better triplet is the following:
- If player A selects T=(X,Y,Z), player B selects S=(YN,X,Y), where YN is the opposite of Y, i.e., YN=0 if Y=1 and YN=1 if Y=0.
E.g., if player A selects (0,1,0) or (0,1,1), player B selects (0,0,1). For another example, if player A selects (1,1,0) or (1,1,1) player B selects (0,1,1).
How do we understand this? We use a general mathematical model.
A way to understand this is by considering random walks on a directed graph. The graph in this game has 8 vertices, the 8 possible triplets. It has 16 edges, i.e., pairs of vertices, with associated probabilities 1/2. Given any triplet, there are two possible tosses which lead to two possible edges. (Note that some edges go from the triplet to itself!)
E.g., there are two edges leading away from (1,1,0),
\((1,1,0) \to (1,0,0), \quad (1,1,0) \to (1,0,1)\)
or, from (1,1,1)
\((1,1,1) \to (1,1,0), \quad (1,1,1) \to (1,1,1)\)
One mathematical model for uses an adjacency matrix M, containing transition probabilities from vertex to vertex.
- We set M(i,j) to the probability to go from triplet j to triplet i (i.e., to reach triplet i from triplet j) in one toss. So we have a matrix M of transition probabilities.
Now imagine starting a lot of experiments by walking from a start vertex to subsequent vertices with the given probabilities. The experiments select the start vertex according to a probability vector P, i.e., vertex i is selected with probability P(i).
- If the distribution of vertices in the experiments is P at a step. Then the matrix multiplication MP will compute the distribution of probabilities at the next step.
Let us do a test in Euler Math Toolbox. First, we generate the adjacency matrix M for our game. Then we start at one specific node and compute the distribution after three steps.
>function makeM () ...
$M = zeros(8,8);
$for i1=0 to 1;
$ for i2=0 to 1;
$ for i3=0 to 1;
$ for j1=0 to 1;
$ for j2=0 to 1;
$ for j3=0 to 1;
$ i=4*i1+2*i2+i3;
$ j=4*j1+2*j2+j3;
$ if i2==j1 and i3==j2 then
$ M[j+1,i+1]=1/2;
$ endif;
$ end;
$ end;
$ end;
$ end;
$ end;
$end;
$return M;
$endfunction
>M=makeM;
>shortest M
0.5 0 0 0 0.5 0 0 0
0.5 0 0 0 0.5 0 0 0
0 0.5 0 0 0 0.5 0 0
0 0.5 0 0 0 0.5 0 0
0 0 0.5 0 0 0 0.5 0
0 0 0.5 0 0 0 0.5 0
0 0 0 0.5 0 0 0 0.5
0 0 0 0.5 0 0 0 0.5
>p=zeros(8)'; p[1]=1; p'
[1, 0, 0, 0, 0, 0, 0, 0]
>p=M.p; p'
[0.5, 0.5, 0, 0, 0, 0, 0, 0]
>p=M.p; p'
[0.25, 0.25, 0.25, 0.25, 0, 0, 0, 0]
>p=M.p; p'
[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125]
The function to generate the matrix M is not the most elegant one. It might be better to use a recursion than a loop. After we generate the matrix, we start with a „distribution“ which puts everything into the first triplet (actually that is (0,0,0)). After only three steps, we see that the probability to reach each triplet is equal.
Let us now model Penney’s game.
We have two triplets T and S (vertex numbers i and j) which lead nowhere. I.e., if those states are met we have found a case where T or S are hit.
We modify the adjacency matrix accordingly and delete all edges leading away from T and S and connect T and S to themselves with probability 1. This is a modified adjacency matrix M(i,j). We now have to look at the following limit.
\(P = \lim_{n \to \infty} M_{i,j}^n P_0\)
with
\(P_0 = (1/8,\ldots,1/8)^T\)
which is our start distribution.
Let us simulate that in Euler Math Toolbox. We select the triplets T=(0,1,0) (third element of p) and S=(0,0,1) (second element of p) which according to our rule should be superior.
>M=makeM;
>M[,2]=0; M[2,2]=1;
>M[,3]=0; M[3,3]=1;
>shortest M
0.5 0 0 0 0.5 0 0 0
0.5 1 0 0 0.5 0 0 0
0 0 1 0 0 0.5 0 0
0 0 0 0 0 0.5 0 0
0 0 0 0 0 0 0.5 0
0 0 0 0 0 0 0.5 0
0 0 0 0.5 0 0 0 0.5
0 0 0 0.5 0 0 0 0.5
>p=ones(8)'/8; p'
[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125]
>p=M.p; p'
[0.125, 0.25, 0.1875, 0.0625, 0.0625, 0.0625, 0.125, 0.125]
>p=M.p; p'
[0.09375, 0.34375, 0.21875, 0.03125, 0.0625, 0.0625, 0.09375,
0.09375]
>loop 1 to 100; p=M.p; end;
>p'
[0, 0.666667, 0.333333, 0, 0, 0, 0, 0]
Indeed, the two selected triplets catch all the distribution, and S=(0,0,1) is indeed twice as good as T=(0,1,0). I.e., player B will win twice as often.
Things get worse for T=(0,0,0) and S=(1,0,0). S is seven times as good as T! There are other combinations which are three times as good.
Due to the structure of the problem, the limit P will have only non-zero entries for T and S. The probability to be in any other triplet will tend to 0. T and S will catch everything.
But can we compute the winning chance for S without a simulation? For that we define
- w(i) as the chance to reach S before T when starting at triplet i.
We are using the following properties of w.
- w(i) = 1 for the vertex S with number i.
- w(j) = 0 for the vertex T with number j.
- w satisfies
\(w = M_{i,j}^T \, w\)
We are searching for a specific eigenvector. The following function of EMT computes w given and adjacency matrix M and i,j, and returns the probability to reach vertex i before vertex j.
>function getw (M,i,j) ...
$if i==j then return 0; endif;
$Mt=M;
$Mt[,i]=0; Mt[i,i]=1;
$Mt[,j]=0; Mt[j,j]=1;
$V = eigenspace(Mt',1);
$c = V[[i,j]]\[1;0];
$return sum((V.c)')/cols(Mt);
$endfunction
>M = makeM();
% Let us try our simulated examples.
>fraction getw(M,2,3), fraction getw(M,5,1)
2/3
7/8
The simulated example from above works, as well as another example which takes T=(0,0,0) and S=(1,0,0).
For the next step, we compute all probabilities that the triplet number i appears before the triplet number j when starting from a random triplet.
>function solvePG () ...
$M = makeM();
$W=zeros(8,8);
$for i=1 to 8;
$ for j=1 to 8;
$ W[i,j]=getw(M,i,j);
$ end;
$end;
$return W;
$endfunction
>W=solvePG();
>fracformat(7); W, defformat;
0 1/2 2/5 2/5 1/8 5/12 3/10 1/2
1/2 0 2/3 2/3 1/4 5/8 1/2 7/10
3/5 1/3 0 1/2 1/2 1/2 3/8 7/12
3/5 1/3 1/2 0 1/2 1/2 3/4 7/8
7/8 3/4 1/2 1/2 0 1/2 1/3 3/5
7/12 3/8 1/2 1/2 1/2 0 1/3 3/5
7/10 1/2 5/8 1/4 2/3 2/3 0 1/2
1/2 3/10 5/12 1/8 2/5 2/5 1/2 0
The non-transitivity of the problem means that in each column there is a value >1/2. We can select this value and print the corresponding triplet in human readable form.
>function printtriplet (i) ...
$s = ")"; i=i-1;
$if mod(i,2) then s=",1"+s; else s=",0"+s; endif;
$i = floor(i/2);
$if mod(i,2) then s=",1"+s; else s=",0"+s; endif;
$i = floor(i/2);
$if mod(i,2) then s="(1"+s; else s="(0"+s; endif;
$return s;
$endfunction
>function printPG (W) ...
$for j=1 to 8;
$ w=W[,j]';
$ e=extrema(w);
$ printtriplet(j) + " -> " + printtriplet(e[4]),
$end;
$endfunction
% We get the well known solution of the game.
>printPG(W)
(0,0,0) -> (1,0,0)
(0,0,1) -> (1,0,0)
(0,1,0) -> (0,0,1)
(0,1,1) -> (0,0,1)
(1,0,0) -> (1,1,0)
(1,0,1) -> (1,1,0)
(1,1,0) -> (0,1,1)
(1,1,1) -> (0,1,1)
This is exactly the well-known rule that you find also in the Wikipedia article.
