Yahtzee!

Garrett Clarke gave the standard MarPkov chain / linear algebra solution. Here is a more elementary solution, without the use of linear algebra techniques.

General strategy

Just like Garrett did, we can consider 5 "states", depending on how many dice we are keeping aside. Of course, for the first roll we have state "zero".

We will calculate

• $p_{ij}$ , the probability of getting from state $i$ to state $j$ .
• $E_i$ , the expected number of turns to get from state $i$ to Yahtzee.

It should be clear immediately that $p_{ij} = 0$ for $j < i$ . Also, $E_5 = 0$ because if we have Yahtzee there are no more rolls left.

The crucial step in the calculation is the fact that $E_i = 1 + \sum_j p_{ij} E_j:$ the number of rolls needed is one (the current roll) plus the weighted average of the rolls that will be needed afterward.

Calculation of $E_4$

To see how this pans out, suppose that we have rolled four of a kind: $\langle a, a, a, a, b\rangle$ , with $a \not = b$ . We keep the four $a$ 's behind, and re-roll the one die with a different value. Let $x$ be the new value of this die.

There are six possible outcomes, which we classify as follows:

• $x = a$ , with probability 1:6. We have rolled Yahtzee (state 5).
• $x \not= a$ , with probability 5:6. We still have four of a kind (state 4).

Thus $p_{45} = \tfrac16$ and $p_{44} = \tfrac56$ . The expected number of rolls from state 4 is $E_4 = 1 + p_{44}E_4 + p_{45}E_5; \\ E_4 = 1 + \tfrac56E_4;$ remember that $E_5 = 0$ . Solve this to find $\tfrac16E_4 = 1\ \ \ \ \therefore\ \ \ \ \ E_4 = 6.$

Thus from state 4 we expect to need six rolls to get Yahtzee.

Calculation of $E_3$

If we have rolled $\langle a, a, a, b, c\rangle$ (with $b$ and $c$ possibly equal), we re-roll two dice with outcomes $x, y$ . There are $6^2 = 36$ possible outcomes in three categories:

• $x = y = a$ . This is Yahtzee. The probability is $p_{35} = 1/6^2 = \tfrac1{36}$ .
• $x = a$ or $y = a$ but not both. This gets us to state four. Since there are two dice involved and the other die could be any of five values, the probability of this happening is $p_{34} = 2\cdot 5/6^2 = \tfrac5{18}$ .
• $x, y \not= a$ . This leaves us in state 3. Since $x$ and $y$ each has five possible values, $p_{33} = 5^2/6^2 = \tfrac{25}{36}$ .

The equation for $E_3$ becomes $E_3 = 1 + p_{33}E_3 + p_{34}E_4 + p_{35}E_5 = 1 + \tfrac{25}{36}E_3 + \tfrac{5}{18}E_4;$ substituting $E_4 = 6$ and solving we get $\tfrac{11}{36}E_3 = 1 + \tfrac5{18}\cdot 6\ \ \ \ \therefore\ \ \ \ 11 E_3 = 36 + 60 = 96\ \ \ \ \therefore\ \ \ \ E_3 = \frac{96}{11} = 8 \tfrac{8}{11}.$

Calculation of $E_2$

And so we continue. If we have two $a$ 's and re-roll three dice, there are $3^6 = 216$ possible outcomes in six categories.

• $\langle a, a, a\rangle$ and we get Yahtzee. $p_{25} = 1/6^3 = \tfrac1{216}$ .
• $\langle a, a, b\rangle$ gets us to state 4. Since there are three possible dice that could show $b$ , and five possible values for $b$ , this gives $p_{24} = 3\cdot 5/6^3 = \tfrac{5}{72}$ .
• $\langle a, b, c\rangle$ (with $b, c$ possibly equal) gets us to state 3. There are possible dice to show $a$ , and five possible values for each of $b, c$ , so that we have $3\cdot 5^2 = 75$ outcomes in this category.
• $\langle b, b, b\rangle$ . This interesting situation in which we don't roll any $a$ still gets us to state 3. (Nobody said we should keep the same dice as before...) There are 5 possible values for $b$ , so that this adds 5 more outcomes to get us to state 3. Combining with the previous category, we get $p_{23} = (75 + 5)/6^3 = \tfrac{10}{27}$ .
• $\langle b, b, c\rangle$ with 60 possible arrangements and $\langle b, c, d$ with 60 possible arrangements accounts for the remaining $216 - 1 - 15 - 75 - 5 = 120$ outcomes. Thus $p_{22} = 120/6^3 = \tfrac 59$ .

We can now write and solve the equation for $E_2$ : $E_2 = 1 + p_{22}E_2 + p_{23}E_3 + p_{24}E_4 + p_{25}E_5; \\ E_2 = 1 + \tfrac59 E_2 + \tfrac{10}{27}\cdot 8 \tfrac{8}{11} + \tfrac{5}{72}\cdot 6; \\ E_2 \approx 10.46.$ In other words, once we have two dice with the same value, we expect to roll 10.46 more times to get Yahtzee.

Calculation $E_0$

You should get the idea now... it is good practice to categorize the 7776 possible outcomes with 5 dice:

• $\langle a, a, a, a, a\rangle$ : 6
• $\langle a, a, a, a, b\rangle$ : 150
• $\langle a, a, a, b, b\rangle$ : 300
• $\langle a, a, a, b, c\rangle$ : 1200
• $\langle a, a, b, b, c\rangle$ : 1800
• $\langle a, a, b, c, d\rangle$ : 3600
• $\langle a, b, c, d, e\rangle$ : 720

This gives the probabilities $p_{00} = \tfrac{5}{54}$ ; $p_{02} = \tfrac{25}{36}$ ; $p_{03} = \tfrac{125}{648}$ ; $p_{04} = \tfrac{25}{1296}$ ; and $p_{05} = \tfrac{1}{1296}$ .

Use this to write the equation for $E_0$ and solve. You find $E_0 \approx 11.09$ , which we round off to $\boxed{11}$ .

What about the matrices?

Garrett's solution uses matrices; essentially the values $E_i$ are packaged into a vector $\mathbf{e}$ and the probabilities $p_{ij}$ become a matrix $\mathbf{P}$ . The four equations $E_i = 1 + \sum_j p_{ij} E_j$ become the single vector equation $\mathbf{e} = \mathbf{1} + \mathbf{P}\,\mathbf{e}$ which is algebraically rearranged as $\mathbf{e} = (\mathbf{I} - \mathbf{P})^{-1} \mathbf{1}.$ The question is, of course, how to calculate this... well, you need the same calculations as we used above for solving for $E_i$ . The linear algebra approach is elegant and more abstract, but ultimately does not save work.

This problem can be solved through the proper use of transition matrices. We can consider ourselves to be in 1 of 5 states when rolling:

• State 1: Keep 0 dice aside

• State 2: Keep 2 dice aside

• State 3: Keep 3 dice aside

• State 4: Keep 4 dice aside

• State 5: Keep 5 dice aside (Yahtzee)

These states make what is known as a Markov Chain. This means that the probability to get from the current state to the next state is not affected by how it got to the current state. We start by filling out a matrix that contains our probabilities to get from one state to another.

$T = \begin{bmatrix} \frac{5}{54} & \frac{25}{36} & \frac{125}{648} & \frac{25}{1296} & \frac{1}{1296} \\ 0 & \frac{5}{9} & \frac{10}{27} & \frac{5}{72} & \frac{1}{216} \\ 0 & 0 & \frac{25}{36} & \frac{5}{18} & \frac{1}{36} \\ 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$

Each row represents your current state and each column represents your next possible state. The fractions in each column represent the probability that you will reach that state on your next roll, given that you are in another state. For example, if I was currently holding 2 dice back, the chance that I would be holding 4 dice aside after the next roll would be $\frac{5}{72}$ , because it is in the 2nd row and the 4th column, or $T_{2,4}$ .

To find the expected value, we need to find the probability that we have reached the final state after each roll. Since once we reach the last state we’re done, we can remove the last row and column from our matrix because they are trivial and make calculation harder.

$T = \begin{bmatrix} \frac{5}{54} & \frac{25}{36} & \frac{125}{648} & \frac{25}{1296} \\ 0 & \frac{5}{9} & \frac{10}{27} & \frac{5}{72} \\ 0 & 0 & \frac{25}{36} & \frac{5}{18} \\ 0 & 0 & 0 & \frac{5}{6} \end{bmatrix}$

Finding the probability that you'll end up in a given state after $n$ rolls is as easy as finding $T^n$ , then reading the probabilities that the resultant matrix provides us with. We now can use the expected value formula for transition matrices to find our answer. Where $\tau = \begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix}$ , $I$ is the Identity Matrix, and $\mathbf{1}$ is a column vector of all 1s:

$E(Yahtzee) = \tau (I+T+T^2+T^3+\dots) \mathbf{1} = \tau (I-T)^{-1} \mathbf{1}$

$E(Yahtzee) = \begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 54/49 & 675/392 & 1500/539 & 94575/17248 \\ 0 & 9/4 & 30/11 & 965/176 \\ 0 & 0 & 36/11 & 60/11 \\ 0 & 0 & 0 & 6 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \approx 11.09$

This means that following this method should give you a Yahtzee in approximately $\boxed{11}$ rolls.