I recently was asked about waiting times in the game of Yahtzee. If you do not know the game it suffices to say that you throw 5 dice, and one of the goals is to get 5 dice with the same number, a Yahtzee. I wrote about waiting times a long time ago. But let me repeat the main points.
The trick is to use a number of states S0, S1, …, Sn, and probabilities P(i,j) to get from state Si to state Sj. S0 is the starting state, and Sn is the state we want to reach, in our case the Yahtzee. For a first attempt, we use the number 6s we have on out 5 dice. Then we have 6 states, S0 to S5. With a bit of combinatorics, we can compute the probabilities P(i,j) as
\(p_{i,j} = p^{j-i} (1-p)^{n-i-(j-i)} \binom{n-i}{j-i}\)
If we compute that with Euler Math Toolbox we get the following matrix P.
>p=1/6;
>i=(0:5)'; j=i';
% This is the matrix of probabilities to get from i sixes to j sixes.
0.4018776 0.4018776 0.1607510 0.0321502 0.0032150 0.0001286
0.0000000 0.4822531 0.3858025 0.1157407 0.0154321 0.0007716
0.0000000 0.0000000 0.5787037 0.3472222 0.0694444 0.0046296
0.0000000 0.0000000 0.0000000 0.6944444 0.2777778 0.0277778
0.0000000 0.0000000 0.0000000 0.0000000 0.8333333 0.1666667
0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 1.0000000
This matrix allows us to simulate or compute results about probabilities for 6-Yahtzees. E.g., we can start with no 6 in S0. After one dice throw, the first row of P yields the distribution of the expected states. We can do dice throws by applying P to the right of our distribution vector.
>v=[1,0,0,0,0,0].P
0.4018776 0.4018776 0.1607510 0.0321502 0.0032150 0.0001286
% After two more throws, we get the following.
>v.P.P
0.0649055 0.2362559 0.3439886 0.2504237 0.0911542 0.0132721
This tells us that the chance to be in state S5 after three throws is just 1.3%.
How about the average time that we have to wait if we keep throwing the dice until we get a 6-Yahtzee? This can be solved by denoting the waiting time from state Si to S5 by w(i) and observe
\(w_i = p_{i,n} + \sum_{j \ne n} p_{i,j} (1+w_j)\)
where n=5 is the final state. Obviously, w(5)=0. Moreover, the sum of all probabilities in one row is 1. Thus we get
\(w_i – \sum_{j=1}^{n-1} w_j = 1\)
Let us solve this system in Euler Math Toolbox.
>B=P[1:5,1:5];
>w=(id(5)-B)\ones(5,1)
13.0236615
11.9266963
10.5554446
8.7272727
6.0000000
The average waiting time for a 6-Yahtzee is approximately 13 throws. If you already got 4 sixes, the average waiting time for the fifth is indeed 6.
We can interpret this in another way. Observe
\(w = (I-B)^{-1} \cdot 1 = (I+B+B^2+\ldots) \cdot 1\)
The sum converges because the norm of B is clearly less than 1. So we interpret this as a process
\(w_{n+1} = B \cdot (w_n + 1)\)
Suppose a waiting room. We have w(n,i) persons in state Si at time n. Now, one more person arrives at each state and we process the states according to our probabilities. On the long run, the number of persons in state S0 will become the waiting time to get out of the system into the final state.
Unfortunately, the probabilities are not that easy to compute when we ask for a Yahtzee of any kind. E.g., if we have 66432 we will keep the two sixes as 66. But we may throw 66555 and switch to keep 555. There is a recursion for the probability to get from i same dice to j same dice. I computed the following matrix which replaces the matrix P above.
>P
0.0925926 0.6944444 0.1929012 0.0192901 0.0007716
0.0000000 0.5555556 0.3703704 0.0694444 0.0046296
0.0000000 0.0000000 0.6944444 0.2777778 0.0277778
0.0000000 0.0000000 0.0000000 0.8333333 0.1666667
0.0000000 0.0000000 0.0000000 0.0000000 1.0000000
Note that I have only the states S1 to S5 here. With the same method, I get the waiting times.
>B=PM[1:4,1:4];
>w=(id(4)-B)\ones(4,1)
11.0901554
10.4602273
8.7272727
6.0000000
Thus we need only about 11 throws to get any Yahtzee. The probability to get one in three throws is now about 4.6%.
>[1,0,0,0,0].PM.PM.PM
0.0007938 0.2560109 0.4524017 0.2447649 0.0460286
Let me explain.
