Expected number of turns for getting six 1's in six dice.

156 Views Asked by At

You have 6 unbiased dice.

What is the expected numbers of turns required to get 1 in all the faces such that whenever you get 1 in any of the dice, you do not roll it for next three turns.

For example, the die faces could be as follows:

Turn 1 $\rightarrow$ 1, 2, 3, 4, 5, 6 (since the first die came up with 1 on top, you do not roll the first die for next 3 turns)

Turn 2 $\rightarrow$ $\mathbf{1} $, 3, 3, 1, 4, 1

Turn 3 $\rightarrow$ $\mathbf{1}$, 5, 6, $\mathbf{1}$, 3, $\mathbf{1}$

Turn 4 $\rightarrow$ $\mathbf{1}$, 4, 4, $\mathbf{1}$, 2, $\mathbf{1}$

Turn 5 $\rightarrow$ 6, 1, 3, $\mathbf{1}$, 5, $\mathbf{1}$

Turn 6 $\rightarrow$ 2, $\mathbf{1}$, 1, 3, 2, 6

and so on. (Numbers in bold indicate that they were not rolled during that turn.)

1

There are 1 best solutions below

2
On BEST ANSWER

We can get quite a good approximation of the expected number of turns as follows:

Call a turn “good” if all dice show a $1$. Let $C_t$ be the event that turn $t$ is good. In the long run, each die shows a $1$ for $\frac4{4+1+1+1+1+1}=\frac49$ of the time, and in the long run the dice are not correlated, so in the long run

$$ \mathsf P(C_t)=\left(\frac49\right)^6=\frac{4096}{531441}\approx0.77\%\;. $$

In the long run, the proportion of good turns is equal to this probability, so the average time between two good turns is the reciprocal of this probability.

If all turns were independent, that would already be the solution, but they aren’t. The conditional probability $\mathsf P(C_t\mid C_{t'})$ for $t - 3 \le t'\le t+3$ is considerably larger than the unconditional probability, so there will sometimes be clusters of good turns, and what we really want is the average time between such clusters, since we’re starting out outside any such cluster.

A cluster of $n$ good turns contains $n-1$ pairs of consecutive good turns. Thus the number of clusters is the number of good turns minus the number of pairs of consecutive good turns. In the long run, the probability for two particular consecutive turns to be good is

$$ P(C_t\cap C_{t+1})=\left(\frac39+\frac19\cdot\frac16\right)^6=\left(\frac{19}{54}\right)^6=\frac{47045881}{24794911296}\approx0.19\%\;, $$

since, for each die, with probability $\frac39$ the first turn has a $1$ that will live until the second turn and with probability $\frac19$ it has a $1$ that needs to be refreshed on the second turn, with probability $\frac16$.

Thus, the expected number of clusters per turn is

\begin{eqnarray} \mathsf P(C_t)-\mathsf P(C_t\cap C_{t+1}) &=& \left(\frac49\right)^6-\left(\frac{19}{54}\right)^6 \\[7pt] &=& \frac{144057095}{24794911296} \\[7pt] &\approx& 0.00581\;, \end{eqnarray}

and thus the expected time to wait for a cluster is approximately the reciprocal,

$$ \frac{24794911296}{144057095}\approx172.12\;. $$

This is only an approximation because some $1$s survive after a cluster ends and thus the probability for the next success to occur right after a cluster is still a bit higher than it is when we start the experiment; but the approximation should be a reasonably good one.

Here’s Java code that simulates the experiment and yields an expected number of $173.95\pm0.05$ turns. Note that if we hadn’t accounted for the clusters and just used the reciprocal of the probability for a turn to be good, the resulting estimate of $\left(\frac94\right)^6\approx130$ turns would have been quite a bit off.

If I find the time, I’ll code the Markov chain to get the exact result for comparison.