Tetrahedral dice game

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:

1. 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.
2. Three dice are duplicates. For example: (1,1,1,2)
3. Two dice are duplicates. For example: (1,1,2,3)
4. 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.