Expected number of rolls until all dice are removed

Question

There are $n$ fair dice. They are all tossed every time except the dice that are removed. A dice is removed if $3$ is rolled. What is the expected number of rolls? Any help would be appreciated.

My attempt: Consider the case of two dice. The process ends on step one with probability $\frac{1}{36}$, if one of the dice rolls up $6$ and other doesn't the on average $\frac{10}{36}(1+6)$ more steps are needed. Finally if $6$ doesn't roll up on both of the rolls then $\frac{25}{36}(z+1)$ rolls will be needed where $z$ is the expected number of rolls until both dice are removed. Thus $$z= \frac{1}{36}+\frac{10}{36}(1+6)+\frac{25}{36}(z+1) $$ Is this correct? If it is I can extend it recursively for $n$ dice.

Answer 1

I have a hard time understanding what your event $X_i$ means? Die $i$ removed by what time? Because in the end all of the dice are removed and $X_i=1$ with $p=1$.

If you want to use this approach, you say that you have $n+1$ states (meaning the number of dice left in the game) and you trying to find $r_k=\mathbb E R(k)$, where $R(k)$ is the number or rolls if you start with $k$ dice. You know that $r_0 = 0$ and you can write recursive relations:

$$ \begin{aligned} r_1 &= 1+\frac56r_1 + \frac16r_0 \\ r_2 &= 1+\left(\frac56\right)^2r_2 + 2\left(\frac56\right)\left(\frac16\right)r_1+\left(\frac16\right)^2r_0\\ \ldots \end{aligned} $$

Or you can take a direct approach and calculate the distribution $R(n)$ directly. You can start to calculate the distribution of $R(1)$ by thinking what is the probability that 1 die wasn't remove on first $x$ rolls. And then see that the survival time of at least 1 die from $n$ is a function of survival times of each individual die: $R(n)=f(R_1(1), R_2(1)...,R_n(1))$. Can you see what function is $f$?

Answer 2

$P\text{(one particular dice remains after first $k$ tosses)}=\left(\frac{5}{6}\right)^k$

$P\text{(one particular dice is removed within first $k$ tosses)}=1-\left(\frac{5}{6}\right)^k$

$P\text{(all dice are removed within first $k$ tosses)}=\left(1-\left(\frac{5}{6}\right)^k\right)^n$

$P\text{(all dice are removed within first $k-1$ tosses)}=\left(1-\left(\frac{5}{6}\right)^{k-1}\right)^n$

$P\text{(last dice is removed exactly at the $k^{th}$ toss)}=\left(1-\left(\frac{5}{6}\right)^{k}\right)^n-\left(1-\left(\frac{5}{6}\right)^{k-1}\right)^n$

Now let $X=\text{number of tosses until all dice are removed}$.

$$E(X)=\sum_{k=1}^\infty{k\left(\left(1-\left(\frac{5}{6}\right)^{k}\right)^n-\left(1-\left(\frac{5}{6}\right)^{k-1}\right)^n\right)}$$

And here is a way to approximate $E(X)$ for large $n$.

Let $Y=\text{number of tosses until one particular dice is removed}$.

Consider the curve of the probability density function of $Y$. The $n$ dice are uniformly distributed in the region under this curve, and the right-most dice has a $Y$-value of $E(X)$.

$\left(\frac{5}{6}\right)^{E(X)}=P\left(Y>{E(X)}\right)=(\text{area under the curve to the right of ${E(X)}$})\approx\frac{1}{n+1}\approx{\frac{1}{n}}$

$${E(X)}\approx\frac{\ln{n}}{\ln{\left(\frac{6}{5}\right)}}$$

Technology (e.g. desmos) verifies that

$$\lim_{n\to\infty}\frac{E(X)}{\frac{\ln{n}}{\ln{\left(\frac{6}{5}\right)}}}=1$$