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?
 A: 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.
A: 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$.
A: *

*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
A: 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$$
A: 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.
