We can view this game as a Markov chain<\/a>. At any point in time, we are in a particular state<\/em> 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:<\/p>\n

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

No dice are duplicates. For example: (1,2,3,4). If we ever arrive at this position, the game ends and we win.\n<\/li>\n<\/ol>\n
We can associate each state transition with a probability. For example, suppose we roll (1,1,2,3). We are in the \u201ctwo-duplicate\u201d state. We must re-roll the two 1\u2019s, and four things could happen:<\/p>\n
\n
We roll (2,2) or (3,3) (probability 1\/8). We now have 3 duplicates and the game continues.\n<\/li>\n
We roll (2,3) or (3,2) (probability 1\/8). We now have 4 duplicates and the game ends (we lose).\n<\/li>\n
We roll (1,4) or (4,1) (probability 1\/8). We now have no duplicates and the game ends (we win).\n<\/li>\n
We roll anything else (probability 5\/8). We have 2 duplicates again and the game continues.\n<\/li>\n<\/ul>\n
If we continue in this manner and find all possible transition probabilities between all four states, we obtain the following diagram:<\/p>\n
$\"\"$ <\/a><\/p>\n
We can think of the \u201cthree duplicates\u201d 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\u2019t roll might as well have been our first roll (all numbers are equivalent by symmetry). Therefore, we can represent our transitions as follows:
\n\\[
\nA = \\begin{bmatrix}
\n 1 & \\frac{5}{32} & \\frac{1}{8} & 0 \\\\
\n 0 & \\frac{3}{16} & \\frac{1}{8} & 0 \\\\
\n 0 & \\frac{9}{16} & \\frac{5}{8} & 0 \\\\
\n 0 & \\frac{3}{32} & \\frac{1}{8} & 1
\n\\end{bmatrix},\\qquad
\nx_0 = \\begin{bmatrix}
\n0 \\\\ 1 \\\\ 0 \\\\ 0\\end{bmatrix}.
\n\\]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 \u201cthree-duplicate\u201d 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:
\n\\[
\nx_{k+1} = A x_k,\\quad\\text{for }k=0,1,\\dots
\n\\]The question is: where will we end up on average? This is equivalent to asking for the limit
\n\\[
\nx_\\infty = \\lim_{k\\to\\infty} A^k x_0
\n\\]We can find this limit by performing an eigenvalue decomposition:
\n\\begin{align}
\nA &= V\\Lambda V^{-1} \\\\
\n&= \\begin{bmatrix}
\n 0 & 1 & \\frac{23}{21} & -1 \\\\
\n 0 & 0 & -\\frac{8}{21} & 30 \\\\
\n 0 & 0 & -\\frac{12}{7} & -30 \\\\
\n 1 & 0 & 1 & 1
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n 1 & 0 & 0 & 0 \\\\
\n 0 & 1 & 0 & 0 \\\\
\n 0 & 0 & \\frac{3}{4} & 0 \\\\
\n 0 & 0 & 0 & \\frac{1}{16}
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n 0 & \\frac{9}{20} & \\frac{29}{60} & 1 \\\\
\n 1 & \\frac{11}{20} & \\frac{31}{60} & 0 \\\\
\n 0 & -\\frac{21}{44} & -\\frac{21}{44} & 0 \\\\
\n 0 & \\frac{3}{110} & -\\frac{1}{165} & 0
\n\\end{bmatrix}
\n\\end{align}The limit is therefore:
\n\\begin{align}
\nA^\\infty x_0 &= V \\Lambda^{\\infty} V^{-1}x_0 \\\\
\n&= \\begin{bmatrix}
\n 0 & 1 & \\frac{23}{21} & -1 \\\\
\n 0 & 0 & -\\frac{8}{21} & 30 \\\\
\n 0 & 0 & -\\frac{12}{7} & -30 \\\\
\n 1 & 0 & 1 & 1
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n 1 & 0 & 0 & 0 \\\\
\n 0 & 1 & 0 & 0 \\\\
\n 0 & 0 & 0 & 0 \\\\
\n 0 & 0 & 0 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n 0 & \\frac{9}{20} & \\frac{29}{60} & 1 \\\\
\n 1 & \\frac{11}{20} & \\frac{31}{60} & 0 \\\\
\n 0 & -\\frac{21}{44} & -\\frac{21}{44} & 0 \\\\
\n 0 & \\frac{3}{110} & -\\frac{1}{165} & 0
\n\\end{bmatrix} \\begin{bmatrix}
\n0 \\\\ 1 \\\\ 0 \\\\ 0\\end{bmatrix}\\\\
\n&= \\begin{bmatrix}
\n 0 & 1 \\\\
\n 0 & 0 \\\\
\n 0 & 0 \\\\
\n 1 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n 0 & \\frac{9}{20} & \\frac{29}{60} & 1 \\\\
\n 1 & \\frac{11}{20} & \\frac{31}{60} & 0
\n \\end{bmatrix}
\n\\begin{bmatrix}
\n0 \\\\ 1 \\\\ 0 \\\\ 0\\end{bmatrix} \\\\
\n&= \\begin{bmatrix}
\n\\frac{11}{20} \\\\ 0 \\\\ 0 \\\\ \\frac{9}{20}\\end{bmatrix}
\n\\end{align}In other words, there is a 11\/20, or 55% chance that we will lose and end up in the \u201call duplicate\u201d case, and a 9\/20, or 45% chance that we will win and end up in the \u201call unique\u201d case.\n<\/p><\/div>\n
<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"
This week\u2019s 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 … Continue reading “Tetrahedral dice game”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3347,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[20,8,2],"class_list":["post-3339","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-markov-chains","tag-probability","tag-riddler"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t