Probability of events with retries?

Question

Let's say I want to roll $n$ 20-sided dice, and I want none of those dice to be a 1. I figure that the probability at least one die will be a 1 is $\frac{19}{20}^n$. But now let's say that we will re-roll each individual die that is a 1 up to $r$ times. I want to know 2 things:

1. Given the above, what is the probability one or more of the dice will be a 1?
2. Suppose I play this game a million times. How many dice rolls will a given game make on average? In other words, for each game, I will make $n+t$ dice rolls, where $t$ is the number of retries I've made. What would $t$ be on average?

Answer 1

If I got your question right,

1. Let's consider one game, the probability of getting a $1$ is given by $1-\left( \frac{19}{20} \right)^r$, now the probability of getting at least a $1$ is the complement of getting no $1$s, that is $1-\left(1-1+ \left( \frac{19}{20} \right)^r \right)^n=1-\left( \frac{19}{20} \right)^{nr}$

2. I will ignore the million time thing, since if you take the average of an expectation you end up with the same result (due to unbiasedness of the average estimator). For one game, the probability of throwing the die $k\in [1:r-1]$ times is $\frac{1}{20} \left( \frac{19}{20} \right)^{k-1}$ and the probability of throwing $r$ times is $\left( \frac{19}{20} \right)^{r-1}$ (the last throw can be $1$ or not). A good sanity check is to verify this sums to $1$. To obtain the expectation we compute \begin{align*} &\frac{1}{20} \sum_{k=1}^{r-1} k \left( \frac{19}{20} \right)^{k-1} + r \left( \frac{19}{20} \right)^{r-1}\\ =&\left(\frac{19}{20}\right)^{r - 1} r + \frac{20}{19} \frac{(-19 (19^r - 20^r) - 19^r r)}{20^{r}} \end{align*} by the Arithmetico-geometric formula (and after few steps)

EDIT : I think that my first one is wrong, see Mike Earnest's answer. And by the way you may have to use $r+1$ instead of $r$ in my formula for the second one depending if you are allowed throw the dice $r$ times or re-throw it $r$ times

Answer 2

In order for a die to end up being $1$, it has come up $1$ a total of $r+1$ times in a row. Therefore, each die ends up being one with probability $(1/20)^{r+1}$, so $$ P(\text{at least one die is }1)=1-P(\text{no dice are }1)=\boxed{1-\bigg(1-\frac1{20^{r+1}}\bigg)^n.} $$ To compute the expected number of rolls, we compute the expected number of rolls for each die and multiply by $n$. Let $X$ be the number times a particular die is rolled, and let's compute $P(X> k)$. The die is rolled more than $k$ times if and only if its first $k$ rolls are $1$, and $k<r$. Therefore, $$ P(X>k) = \frac{1}{20^k},\qquad k=0,1,\dots,r. $$ Then the expected value is $$ E[X]=\sum_{k=0}^r P(X>k)=\sum_{k=0}^r \frac{1}{20^k}=\frac{1-(1/20)^{r+1}}{1-1/20}. $$ Therefore, $$ E[\#\text{ of rolls}]=n\cdot E[X]=\boxed{n\cdot \frac{20}{19}\Big(1-\frac{1}{20^{r+1}}\Big).} $$ For example, when $r=0$, the expected number of rolls is $n$. As $r$ tends to infinity, the expected number of rolls tends to $n\cdot \frac{20}{19}$.