This week’s Riddler Classic is a game of four-sided dice:

You have four fair tetrahedral dice whose four sides are numbered 1 through 4.

You play a game in which you roll them all and divide them into two groups: those whose values are unique, and those which are duplicates. For example, if you roll a 1, 2, 2 and 4, then the 1 and 4 will go into the “unique” group, while the 2s will go into the “duplicate” group.

Next, you reroll all the dice in the duplicate pool and sort all the dice again. Continuing the previous example, that would mean you reroll the 2s. If the result happens to be 1 and 3, then the “unique” group will now consist of 3 and 4, while the “duplicate” group will have two 1s.

You continue rerolling the duplicate pool and sorting all the dice until all the dice are members of the same group. If all four dice are in the “unique” group, you win. If all four are in the “duplicate” group, you lose.

What is your probability of winning the game?

My solution:

[Show Solution]

We can view this game as a Markov chain. At any point in time, we are in a particular *state* of the game, and when we re-roll the dice, we transition to a different state. Although there are many possible states (one for each possible way of rolling the four dice), we can use symmetry arguments to reduce the total states to just four. Here they are:

- All dice are duplicates. This includes cases like (1,1,1,1) but also (2,2,3,3). If we ever arrive at this position, the game ends and we lose.
- Three dice are duplicates. For example: (1,1,1,2)
- Two dice are duplicates. For example: (1,1,2,3)
- No dice are duplicates. For example: (1,2,3,4). If we ever arrive at this position, the game ends and we win.

We can associate each state transition with a probability. For example, suppose we roll (1,1,2,3). We are in the “two-duplicate” state. We must re-roll the two 1’s, and four things could happen:

- We roll (2,2) or (3,3) (probability 1/8). We now have 3 duplicates and the game continues.
- We roll (2,3) or (3,2) (probability 1/8). We now have 4 duplicates and the game ends (we lose).
- We roll (1,4) or (4,1) (probability 1/8). We now have no duplicates and the game ends (we win).
- We roll anything else (probability 5/8). We have 2 duplicates again and the game continues.

If we continue in this manner and find all possible transition probabilities between all four states, we obtain the following diagram:

We can think of the “three duplicates” state as our start state. Why? Because we start the game by rolling all four dice. This is mathematically equivalent to rolling three dice, since the value of the die we don’t roll might as well have been our first roll (all numbers are equivalent by symmetry). Therefore, we can represent our transitions as follows:

\[

A = \begin{bmatrix}

1 & \frac{5}{32} & \frac{1}{8} & 0 \\

0 & \frac{3}{16} & \frac{1}{8} & 0 \\

0 & \frac{9}{16} & \frac{5}{8} & 0 \\

0 & \frac{3}{32} & \frac{1}{8} & 1

\end{bmatrix},\qquad

x_0 = \begin{bmatrix}

0 \\ 1 \\ 0 \\ 0\end{bmatrix}.

\]Notice that all columns sum to 1 since the sum of probabilities from every node along outgoing edges must sum to 1. We can view our current state distribution as a column vector that sums to 1. For example, our initial state is given by $x_0$ above, since we start in the “three-duplicate” state with probability 1. Every time we transition to a new state, our new distribution can be found by multiplying our current state by $A$. In other words:

\[

x_{k+1} = A x_k,\quad\text{for }k=0,1,\dots

\]The question is: where will we end up on average? This is equivalent to asking for the limit

\[

x_\infty = \lim_{k\to\infty} A^k x_0

\]We can find this limit by performing an eigenvalue decomposition:

\begin{align}

A &= V\Lambda V^{-1} \\

&= \begin{bmatrix}

0 & 1 & \frac{23}{21} & -1 \\

0 & 0 & -\frac{8}{21} & 30 \\

0 & 0 & -\frac{12}{7} & -30 \\

1 & 0 & 1 & 1

\end{bmatrix}

\begin{bmatrix}

1 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 \\

0 & 0 & \frac{3}{4} & 0 \\

0 & 0 & 0 & \frac{1}{16}

\end{bmatrix}

\begin{bmatrix}

0 & \frac{9}{20} & \frac{29}{60} & 1 \\

1 & \frac{11}{20} & \frac{31}{60} & 0 \\

0 & -\frac{21}{44} & -\frac{21}{44} & 0 \\

0 & \frac{3}{110} & -\frac{1}{165} & 0

\end{bmatrix}

\end{align}The limit is therefore:

\begin{align}

A^\infty x_0 &= V \Lambda^{\infty} V^{-1}x_0 \\

&= \begin{bmatrix}

0 & 1 & \frac{23}{21} & -1 \\

0 & 0 & -\frac{8}{21} & 30 \\

0 & 0 & -\frac{12}{7} & -30 \\

1 & 0 & 1 & 1

\end{bmatrix}

\begin{bmatrix}

1 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 \\

0 & 0 & 0 & 0 \\

0 & 0 & 0 & 0

\end{bmatrix}

\begin{bmatrix}

0 & \frac{9}{20} & \frac{29}{60} & 1 \\

1 & \frac{11}{20} & \frac{31}{60} & 0 \\

0 & -\frac{21}{44} & -\frac{21}{44} & 0 \\

0 & \frac{3}{110} & -\frac{1}{165} & 0

\end{bmatrix} \begin{bmatrix}

0 \\ 1 \\ 0 \\ 0\end{bmatrix}\\

&= \begin{bmatrix}

0 & 1 \\

0 & 0 \\

0 & 0 \\

1 & 0

\end{bmatrix}

\begin{bmatrix}

0 & \frac{9}{20} & \frac{29}{60} & 1 \\

1 & \frac{11}{20} & \frac{31}{60} & 0

\end{bmatrix}

\begin{bmatrix}

0 \\ 1 \\ 0 \\ 0\end{bmatrix} \\

&= \begin{bmatrix}

\frac{11}{20} \\ 0 \\ 0 \\ \frac{9}{20}\end{bmatrix}

\end{align}In other words, there is a 11/20, or 55% chance that we will lose and end up in the “all duplicate” case, and a 9/20, or 45% chance that we will win and end up in the “all unique” case.

I got slightly different coefficients.

For the three duplicates self transition i got 3/16. And the transition from three to two duplicates is correspondingly smaller.

The way I did the 3 duplicates was with 4 throws: select the duplicate value (4 options) select the throw positions (4 options) select the non duplicate (3 options).

p = 3*4*4/4^4 = 3/16

I agree with Tlk – imagine my dismay when Laurent Lessard posted a solution from mine!

Confirming the probability from three duplicates to two: select the location of the duplicates (6 options), then the identity of the duplicates (4 options), then the identity of the two singletons where order matters (3*2 options). P=(6*4*3*2)/(4^4)=9/16.

Aha! I see you just made the edit. Well done!

Thank you both for your comments! Somehow in my mind, 12/64 simplified to 3/32. Oops! I corrected my mistake and updated my solution.

A faster way to get to the final result is to notice that A^infinity (call it L for limit) must be of the form L=

1 1-x 1-y 0

0 0 0 0

0 0 0 0

0 x y 1

where x is the probability of winning starting from 3 duplicates and y is the probability of winning starting from 2 duplicates (which we don’t care about). Then we must have L.A = L, where L.A means matrix multiplication. This yields two equations for x and y, whose solution is x=9/20 and y=29/60.