A general equation for the number of rolls to get from N dice to zero dice

Question

I am trying to understand how to write a general equation for a math problem that came up during a recent game of Warhammer 40k.

The question is: Assume you start with a set of 10 regular 6-sided dice. The entire set of dice will be rolled simultaneously. Any of the dice that roll to a 6 will be removed from the set, and the remaining dice will be re-rolled. This will repeat until there are no dice remaining. How many rolls, mathematically, should this process take?

At first thought I was under the assumption that this would be similar to a binary search algorithm, but rather than decreasing the initial set size by $\frac 12$ per iteration, it would decrease only by $\frac 16$, though I keep coming up with answers that are clearly incorrect (huge numbers, negative numbers.)

What would be the most appropriate way to generalize an equation for this problem for a set of $N$ regular 6-sided dice?

Answer 1

Your intuition is reasonable. The expected number of dice is reduce by a factor $\frac 56$ each roll, so you could ask the number of rolls to get the expected number of dice below $1$. That gives $$10\left(\frac 56\right)^n \lt 1\\n\approx 12.6$$ so you should expect to average $13$ rolls but that is very rough.

A more careful approach is to work upwards. You expect $6$ rolls if you start with one die. If you start with two dice you have $\frac 1{36}$ chance of getting two sixes and being done. You have $\frac {10}{36}$ chance of getting one six and being at one die. You have $\frac {25}{36}$ chance of getting no sixes and being back where you started. If $x$ is the expected number of rolls starting with two dice you then have $$x=\frac 1{36} \cdot 1 + \frac {10}{36} \cdot 7 +\frac {25}{36}(1+x)\\ x=\frac {96}{11}\approx 8.73$$ You can keep going with this to get the expected value for ten dice, but the calculations get long.

Answer 2

At each step you have a new geometrically distributed random variable. Each time with a different probability of success.

If you have $k$ dices, then the success ratio is $1 - \left(\frac{5}{6}\right)^k$, i.e. probability of not getting every dice between $1$ and $5$.

In case $k=1$ this is our regular dice.

Now, the expectation of geometrically distributed random variable is $\mathbb{E} = \frac{1}{p}$, where $p$ - is the probability of success.

Denote $Y_i$ - a number of rolls it takes to "get rid" of a next dice, in case you have $i$ at hand.

Then $$\mathbb{E}(Y_i) = \frac{1}{1 - \left(\frac{5}{6}\right)^i}$$

Since the expectation is linear you have $$\mathbb{E}(Y_{10} + Y_9 + \ldots + Y_1) = \sum\limits_{k=1}^{n = 10} \frac{1}{1 - \left(\frac{5}{6}\right)^k} \approx 21.876$$

Answer 3

The required number of rolls is the maximum of $N$ independent identically distributed random variables with a geometric distribution with parameter $p=\frac16$. The cumulative distribution function for the number $k$ of rolls required for a single die is $1-(1-p)^k$, so the cumulative distribution function for the maximum is $\left(1-(1-p)^k\right)^N$, and the expected value of the maximum is

\begin{eqnarray*} \sum_{k=0}^\infty\left(1-\left(1-(1-p)^k\right)^N\right) &=& -\sum_{k=0}^\infty\sum_{j=1}^N\binom Nj\left(-(1-p)^k\right)^j \\ &=& -\sum_{j=1}^N\binom Nj(-1)^j\sum_{k=0}^\infty(1-p)^{kj} \\ &=& -\sum_{j=1}^N\binom Nj(-1)^j\frac1{1-(1-p)^j}\;. \end{eqnarray*}

This agrees with Ross's result for $N=2$. In your case, $N=10$, Wolfram|Alpha yields

$$ \frac{5002237679837182013478909216}{301979071571007691559239541}\approx16.6\;. $$

Here's Java code to check the result.