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?

• 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

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.

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$.