# “$n$-Yahtzee” question

Suppose that you have $n \geq 1$ standard 6-sided dice. If all the dice display the same number, we call this an $n$-Yahtzee.

1. Roll all the dice. Set aside those dice with the highest mode (Example, for 8 dice if I roll 1 2 4 4 4 5 6 6, set aside the 4s). If two or more are tied, choose one of them. This number will be fixed.
2. For the remaining dice, roll them and set aside those dice matching the number from step 1.
3. Repeat step 2 until you have obtained an $n$-Yahtzee.

Question : What is the average number of rolls (depending on $n$) that it takes to achieve an $n$-Yahtzee?

There are many variants of this question I would also like to consider, judging from the interest received on this question.

-
If you wanted to complicate the calculation you might note that the second roll of your example might produce one 2 and four 3s to go with your saved three 4s: you might then decide to target 3s in future rather than the 4s. – Henry Dec 10 '12 at 20:30
Yes, I would like to answer the "non-optimal play" question though. – Euler....IS_ALIVE Dec 11 '12 at 5:38
after your first roll the n-yahtzee time is the maximum time to make your point on any of the remaining die, and these times are i.i.d. geometric. I think the problem is no harder than figuring out the distribution of the highest mode, but .... – mike Feb 20 '13 at 17:36
I love it this kind of problems! I will try to solve it, but I confess that I find rather low your bounty...I think that the problem deserves more "MSE-Coins". – Matemáticos Chibchas Mar 28 '13 at 1:10
@MatemáticosChibchas Originally there was no bounty. I asked this question in December and basically forgot about it until now! – Euler....IS_ALIVE Mar 28 '13 at 2:33

I believe the question divides into two parts:

1. How many rolls to make a "point" of 2 or more dice with the same number.
2. How many rolls of the remaining dice to achieve that "point".

Given that the rolls of dice are independent geometrically distributed variables we can use:

1. $P(Y)$ is the geometric probability distribution of the number $Y=X−1$ of failures before the first success, supported on the set $\{0,1,2,3,...\}$ in setting the "point". The expected value of this is $E_1=\frac{1−p}{p}$, where p is the probability of setting the point (i.e. getting a pair or better).

2. $R(Z)$ is the distribution for the remaining dice ($r$) to converge on the point. This the maximum of $r$ i.i.d. geometric random variables with $q=\frac{1}{6}$. The answer to Expectation of the maximum of IID geometric random variables gives an expected value of $$\mathrm E_2=\sum_{k\geqslant0}(1-\mathrm P(Z\leqslant k))=\sum_{k\geqslant0}(1-\mathrm P(Y\leqslant k)^r)=\sum_{k\geqslant0}(1-(1-(1-q)^{k+1})^r).$$

The answers below have been checked against an empirical calculation of 999,999 results using a visual basic program. Empirical results are shown italicized.

$n=1$

Any number will do

$$E_1+E_2=0$$

$n=2$

\begin{align}E_1+E_2&=\frac{1-\left(1-\left(\frac{5}{6}\right)\right)}{1-\left(\frac{5}{6}\right)}+\sum_{k\geqslant0}(1-(1-(1-\frac{1}{6})^{k+1})^{2-2})\\ & =\frac{\left(\frac{5}{6}\right)}{\left(\frac{1}{6}\right)}\\ &=5\\ \end{align}

5.00 SD 5.48

I'm confident that this answer is correct since it only relies on setting the point, the term relating to the rolls of 0 dice to match it is 0 - which makes complete sense. Let's see how we go with $n=3$

\begin{align}E_1&=\frac{1-\left(1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)\right)}{1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)}\\ &=\frac{20}{16}\\ &=1.25 \end{align}

1.25 SD 1.68

\begin{align}E_2&=\sum_{k\geqslant0}(1-(1-(1-\frac{1}{6})^{k+1})^{3-2})\\ &=\sum_{k\geqslant0}\left(\frac{5}{6}\right)^{k+1}\\ &=\frac{1}{1-\frac{5}{6}}-1\\ &=5\ \end{align}

5.63 SD 5.49 - this is a little high but only by 0.11 SD

$$E_1+E_2=6.25$$

6.88 SD 5.74

Moving on to $n=4$

\begin{align}E_1&=\frac{1-\left(1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)\left(\frac{3}{6}\right)\right)}{1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)\left(\frac{3}{6}\right)}\\ &=\frac{60}{156}\\ &=0.38 \end{align}

0.39 SD .73

This is going down as expected, with more dice in play pairs are easier to come by.

\begin{align}E_2&=\sum_{k\geqslant0}(1-(1-(1-\frac{1}{6})^{k+1})^{4-2})\\ &=\sum_{k\geqslant0}(1-(1-(\frac{5}{6})^{k+1})^{2})\\ &=\sum_{k\geqslant0}(1-(1-2(\frac{5}{6})^{k+1}+(\frac{5}{6})^{2k+2}))\\ &=2\sum_{k\geqslant0}(\frac{5}{6})^{k+1}-\sum_{k\geqslant0}\left(\left(\frac{5}{6}\right)^2\right)^{k+1}\\ &=2\left(\frac{1}{1-\frac{5}{6}}-1\right)-\left(\frac{1}{1-\frac{25}{36}}-1\right)\\ &=10-\left(\frac{36}{11}-1\right)\\ &=10-\frac{25}{11}\\ &\approx7.73\\ \end{align}

8.31 SD 6.14

$$E_1+E_2\approx8.11$$

8.7 SD 6.19

The real Yahtzee to $n=5$

\begin{align}E_1&=\frac{1-\left(1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)\left(\frac{3}{6}\right)\left(\frac{2}{6}\right)\right)}{1-\left(\frac{5}{6}\right)\left(\frac{4}{6}\right)\left(\frac{3}{6}\right)\left(\frac{2}{6}\right)}\\ &=\frac{120}{1176}\\ &=0.102 \end{align}

0.102 SD 0.336

\begin{align}E_2&=\sum_{k\geqslant0}(1-(1-(1-\frac{1}{6})^{k+1})^{5-2})\\ &=\sum_{k\geqslant0}(1-(1-3(\frac{5}{6})^{k+1}+3(\frac{5}{6})^{2(k+1)}-(\frac{5}{6})^{3(k+1)}))\\ &=3\sum_{k\geqslant0}(\frac{5}{6})^{k+1}-3\sum_{k\geqslant0}(\frac{5}{6})^{2(k+1)}+\sum_{k\geqslant0}(\frac{5}{6})^{3(k+1)}\\ &=3\left(\frac{1}{1-\frac{5}{6}}-1\right)-3\left(\frac{1}{1-\frac{25}{36}}-1\right)+\left(\frac{1}{1-\frac{125}{216}}-1\right)\\ &=15-\frac{75}{11}+\frac{125}{91}\\ &\approx9.56\\ \end{align}

10.0 SD 6.40

$$E_1+E_2\approx10.1$$

I think these are the correct answer even though the empirical results are a bit high for all of them (but well within 1 standard deviation).

The program I used to generate it is a 9kB file which I would post if I knew how. The spreadsheet it generates, however, is 165MB.

For interest, here are the results of the 5-Yahtzee using 3 slightly different algorithms. The D (for dumb) algorithm sets the point at the highest mode on the first roll (i.e. it will match a single die), the normal algorithm sets the point on the first pair or better, the S (for smart) sets the point on the first pair or better but will switch if 3 of a kind come up on the other 3 dice.

The means of the three algorithms are 10.24, 10.16 and 10.10 respectively.

With the 3 rolls you get in a game of Yahtzee you have a 0.0456 chance of getting a Yahtzee on any given turn. You get 13 turns in a game so if you go for nothing else (which is probably not a winning strategy), you have a 0.455 chance of at least one per game. In a 4 person game there is a 0.911 chance of at least one.

-
I just wanted to point your attention to meta.math.stackexchange.com/questions/4666/…. It's designed for you to work on long answers before posting on the main site. – Jason DeVito Mar 27 '13 at 4:33
Thanks @JasonDeVito – Dale M Mar 27 '13 at 4:39
Looking back, my comment appears to be quite pushy, so I apologize for that - I didn't mean anything negative by it. Some people don't like to see the same answer edited and re-edited several times. Some interpret it as a ploy to get reputation (as any edit bumps your answer to the top of the list) and some just find it annoying. That said, a few edits here and there certainly aren't a big deal, so feel free to ignore me completely ;-) – Jason DeVito Mar 27 '13 at 4:46