# Expected number of rolls to get all sixes

I'm struggling with the following problem:

I have $N$ balanced 6-sided dice. I roll the dice simultaneously, and remove any sixes that occur. I roll the remaining dice again, and remove any more sixes. I repeat the process until there are no dice remaining. What is the expected number of rolls this will take?

So far I have calculated that by the $n^{th}$ dice roll there will be $N\left(\frac56\right)^n$ dice remaining: If we start with $N$ dice, on the first roll we expect $\frac{N}{6}$ sixes. Therefore, on the second roll we expect to have $N-\frac{N}{6}$ dice and hence expect $\frac{5N}{36}$ sixes, meaning after the second roll there are $\frac{25}{36}N$ dice remaining. Repeating this calculation gives the sequence $N, \frac{25}{36}N, \frac{125}{216}N...$ which is equal to $N\left(\frac56\right)^n$ where $n$ is the roll number. I'm struggling with the next part: My thinking is we must find the expected number of rolls $n$ such that $N\left(\frac56\right)^n\lt0.5$, and therefore $n>\frac{\ln(\frac{0.5}{N})}{\ln(\frac56)}$. Taking $N$ to be
$8$, the expected number of rolls is then about $15.21$. I used MATLAB to run the experiment $200,000$ times, and it gave me an average number of rolls of $15.4$. I seem to be close to the right answer, but I'm not sure what I've done wrong. What is the solution?

• why are you doing less than $0.5$? Nov 7, 2017 at 19:55
• @JohnLou I thought that, since they are discrete values, I should use a value that will round down to $0$ rather than round up to $1$ Nov 7, 2017 at 19:57

• The probability a particular die has not shown a $6$ in the first $k$ rolls is $\left(\frac{5}{6}\right)^k$

• The probability a particular die has shown a $6$ in the first $k$ rolls is $1- \left(\frac{5}{6}\right)^k$

• The probability all $N$ dice have shown a $6$ in the first $k$ rolls is $\left(1- \left(\frac{5}{6}\right)^k\right)^N$

• The probability all $N$ dice have shown a $6$ in $k$ rolls but not in $k-1$ rolls is $\left(1- \left(\frac{5}{6}\right)^k\right)^N - \left(1- \left(\frac{5}{6}\right)^{k-1}\right)^{N}$

This will give a mean of $$\sum_{k=0}^{\infty} \left(1- \left(1- \left(\frac{5}{6}\right)^k\right)^N\right)$$

For $N=8$ this seems to suggest a mean of about $15.40694347788$, close to your simulation result

• This also agrees with my computation using an absorbing Markov chain.
– amd
Nov 7, 2017 at 20:27
• @amd I’d be keen to see that solution, if you have the time to write it out. Nov 7, 2017 at 22:22
• How do you get the 4th probability or the expected value? Nov 7, 2017 at 23:21
• @TheoreticalEconomist It’s easy enough to throw up a worked example for fixed $N$, but I’d like to see if I can generalize this Markov chain-based solution before posting an answer.
– amd
Nov 7, 2017 at 23:35
• I believe the last probability should be using $k-1$ and $N$ as the powers in the second term rather than vice-versa?
– caf
Nov 8, 2017 at 5:05

The random variable you are considering is the maximum of $N$ independent $\mathrm{Geometric}(1/6)$ random variables. One way to see this is by imagining the sequences of dice rolls in the following way, where $\bullet$ represents a non-six, $\times$ represents the first $6$ rolled, and $\cdot$ indicates that no roll occurred:

\begin{array}{ccccccc} \text{roll}&1&2&3&\cdots&N-1&N\\ 1&\bullet&\times&\bullet&\cdots&\bullet&\bullet\\ 2&\bullet&\cdot&\bullet&\cdots&\bullet&\times\\ 3&\bullet&\cdot&\times&\cdots&\bullet&\cdot\\ 4&\bullet&\cdot&\cdot&\cdots&\bullet&\cdot\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ M&\cdot&\cdot&\cdot&\cdots&\times&\cdot \end{array}

Then the roll $M$ on which the last six is rolled is just $\max\{X_{i}:1\leq i\leq N\}$, where $X_{i}$ is the first roll on which the $i$th dice lands on 6 (so in the diagram above, $X_{2}=1,$ $X_{3}=3,$ $X_{N}=2,$ and $X_{N-1}=M$).

Now that we know the distribution of $M$, we can compute: $$P(M\leq m)=P\left(\bigcap_{i=1}^{N}\{X_{i}\leq m\}\right)=\prod_{i=1}^{N}P(X_{i}\leq m)=\left(1-\left(\frac{5}{6}\right)^{m}\right)^{N}.$$

Next we apply the formula, valid for any integer-valued, nonnegative random variable $X$, $E(X)=\sum_{k=0}^{\infty}P(X>k)$, which gives $$E(M)=\sum_{m=0}^{\infty}P(M>m)=\sum_{m=0}^{\infty}1-\left(1-\left(\frac{5}{6}\right)^{m}\right)^{N}=\sum_{m=0}^{\infty}\frac{6^{mN}-(6^{m}-5^{m})^{N}}{6^{mN}}.$$ Applying the Binomial Theorem, $(6^{m}-5^{m})^{N}=\sum_{k=0}^{N}\binom{N}{k}6^{mk}(-5^{m})^{N-k}$, so $6^{mN}-(6^{m}-5^{m})^{N}=\sum_{k=0}^{N-1}\binom{N}{k}6^{mk}(-1)^{N-k-1}5^{m(N-k)}$. Then interchanging summation (which is valid since $E(M)\leq 6N<\infty$): $$E(M)=\sum_{k=0}^{N-1}\binom{N}{k}(-1)^{N-k-1}\sum_{m=0}^{\infty}\left(\frac{5}{6}\right)^{m(N-k)}.$$ Since $(5/6)^{N-k}<1$ for all $0\leq k\leq N-1,$ we may apply the geometric summation formula to get $$E(M)=\sum_{k=0}^{N-1}\binom{N}{k}(-1)^{N-k-1}\frac{1}{1-(5/6)^{N-k}}=\sum_{k=0}^{N-1}\binom{N}{k}(-1)^{N-k-1}\frac{6^{N-k}}{6^{N-k}-5^{N-k}}.$$ I can't simplify this last formula, but it looks like it grows roughly logarithmically.

• +1 for the insight that this is an order-statistic problem.
– amd
Nov 8, 2017 at 0:04

Letting $N$ be the number of dice and $\beta = \frac{5}{6}$ the probability of not rolling a six, with reasoning identical to that of @Henry we get

$$P_k = \left(1-\beta^k\right)^N - \left(1-\beta^{k-1}\right)^N \enspace.$$

as the probability all dice have shown a six in $k$ rolls but not in $k-1$ rolls. Therefore the expected number of rounds is

$$\sum_{k \geq 1} P_k k = \sum_{k \geq 1} \left[\left(1-\beta^k\right)^N - \left(1-\beta^{k-1}\right)^N\right] k \enspace.$$

Applying the binomial theorem twice and canceling the two identical constant terms, we get

$$\sum_{1 \leq i \leq N} \binom{N}{i} \frac{(-1)^i}{\beta^i - 1} \enspace,$$

having noted that for $0 < \alpha < 1$,

$$\sum_{k \geq 1} \alpha^k k = \frac{\alpha}{(\alpha-1)^2} \enspace.$$

For $N=8$, we get approximately $15.406943477881558$.

Did not find analytical solution. Here is the deduction:

$$f(N)=1+\sum_{i=0}^{N}{{N}\choose{i}}\times\Big(\frac{1}{6}\Big)^i\times\Big(\frac{5}{6}\Big)^{N-i}\times f(N-i)$$

$$f(0)=0$$

Here's a quick intuitive calculation. Let $e_n$ be the expected number of rolls to eliminate $n$ dice. On each roll, about one sixth of the dice are eliminated. So, $$\begin{eqnarray*} e_n&\approx& 1+e_{\frac 56 n}\\ &\approx&2+e_{(\frac56)^2 n}\\ &\ldots&\\ &\approx&k+e_{(\frac56)^k n} \end{eqnarray*}$$ Taking $e_1\approx0$, this gives $$e_n\approx\frac{\log n}{-\log\frac56}.$$ It turns out this approximation is surprisingly close. See this wonderful article by Bennett Eisenberg for a full discussion.

The responses to this question seem to have a murkiness due to talking about non-integer numbers of dice and defining when you have reached Zero dice left. So I went for the results experimentally by having a (Pelles) C program do a million simulations, recording the number of total tosses it took for all N dice to show 6, and dividing by the number of trials.

The Code snippet, and the results for 1 to 100 dice is below. The results agree with the calculated results for small numbers of dice, and shows the slow increase in tosses as the number of dice increases.

------------------------- C code for dice tossing experiment -----------

NumTrials=100000; for (N=1;N<=100;N++) {

             printf(" # of Dice = %d\n ", N );

for (i=0;i<10; i++) Counts[i]=0;


for (Trials=0;Trials < NumTrials; Trials++) { //Trial loop

  NewNum=N;    //start with N dice
NewTrial=1;

while (NewNum>0)  // trial is over when all N dice have hit 6.
{
next=NewNum;

for(i=0;i<next;i++)
{

r=rand()%6;    // result of the toss is a random number mod 6, i.e.
// a random number from 0 to 5
if (r==0)NewNum--;   //reduce the number of remaining dice by 1whenever
// a dice comes up 6.  (i.e. 0 mod 6

Counts[r+1]++;    // check the random numb gen

}

Counts[0]++;         // Record that another toss has happened.

}//end of 'while next>0.  on to next trial

}  // end of for Trial= .. loop

Avg=(double)Counts[0]/NumTrials;

fprintf(fp," N= %d, avg= %.2f \n", N, Avg);


----------------------- RESULTS ----------------------- C:\Pelles C Projects\rolling 6's.dat

trials = 200000

N= 1, avg= 6.01 N= 2, avg= 8.73 N= 3, avg= 10.56 N= 4, avg= 11.93 N= 5, avg= 13.02 N= 6, avg= 13.94 N= 7, avg= 14.72 N= 8, avg= 15.39 N= 9, avg= 16.01 N= 10, avg= 16.57 N= 11, avg= 17.07 N= 12, avg= 17.52 N= 13, avg= 17.95 N= 14, avg= 18.35 N= 15, avg= 18.70 N= 16, avg= 19.06 N= 17, avg= 19.37 N= 18, avg= 19.66 N= 19, avg= 19.95 N= 20, avg= 20.23 N= 21, avg= 20.50 N= 22, avg= 20.76 N= 23, avg= 20.98 N= 24, avg= 21.21 N= 25, avg= 21.42 N= 26, avg= 21.66 N= 27, avg= 21.88 N= 28, avg= 22.01 N= 29, avg= 22.22 N= 30, avg= 22.41 N= 31, avg= 22.59 N= 32, avg= 22.72 N= 33, avg= 22.90 N= 34, avg= 23.09 N= 35, avg= 23.23 N= 36, avg= 23.39 N= 37, avg= 23.56 N= 38, avg= 23.67 N= 39, avg= 23.83 N= 40, avg= 24.00 N= 41, avg= 24.11 N= 42, avg= 24.22 N= 43, avg= 24.37 N= 44, avg= 24.49 N= 45, avg= 24.62 N= 46, avg= 24.72 N= 47, avg= 24.86 N= 48, avg= 24.93 N= 49, avg= 25.07 N= 50, avg= 25.17 N= 51, avg= 25.30 N= 52, avg= 25.37 N= 53, avg= 25.50 N= 54, avg= 25.60 N= 55, avg= 25.67 N= 56, avg= 25.79 N= 57, avg= 25.89 N= 58, avg= 25.98 N= 59, avg= 26.08 N= 60, avg= 26.17 N= 61, avg= 26.26 N= 62, avg= 26.35 N= 63, avg= 26.47 N= 64, avg= 26.53 N= 65, avg= 26.61 N= 66, avg= 26.68 N= 67, avg= 26.76 N= 68, avg= 26.86 N= 69, avg= 26.94 N= 70, avg= 27.02 N= 71, avg= 27.09 N= 72, avg= 27.14 N= 73, avg= 27.26 N= 74, avg= 27.31 N= 75, avg= 27.41 N= 76, avg= 27.46 N= 77, avg= 27.53 N= 78, avg= 27.60 N= 79, avg= 27.68 N= 80, avg= 27.71 N= 81, avg= 27.80 N= 82, avg= 27.84 N= 83, avg= 27.97 N= 84, avg= 28.03 N= 85, avg= 28.08 N= 86, avg= 28.13 N= 87, avg= 28.21 N= 88, avg= 28.25 N= 89, avg= 28.32 N= 90, avg= 28.39 N= 91, avg= 28.43 N= 92, avg= 28.51 N= 93, avg= 28.55 N= 94, avg= 28.62 N= 95, avg= 28.68 N= 96, avg= 28.72 N= 97, avg= 28.79 N= 98, avg= 28.85 N= 99, avg= 28.88 N= 100, avg= 28.93

• You understand that an uneducated person having no knowledge of mathematics can easily write code for this simulation. What is your contribution towards the analysis of this question? Dec 23, 2017 at 12:20