Expected number of rolls to get all sixes

Question

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?

Answer 1

• 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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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