Suppose we roll a fair die until some face has appeared twice. For instance, we might have a run of rolls 12545 or 636. How many rolls on average would we make? What if we roll until a face has appeared three times?
I calculated the expected value for getting a repeat for a six-sided dice and I got 1223/324 (3.77 tosses). How would we generalize this to an $n$-sided dice? What about $k$-repeats?
Best Answer
Denote by $E_r$ the expected number of additional throws when there are $r$ numbers that we have not yet seen. The $E_r$ satisfy the following recursion: $$E_0=1,\quad E_r=1+{r\over6} E_{r-1}\ .$$ (The next throw shows with probability ${r\over6}$ a new number instead of one we have already seen.)
Probably there is a closed formula for the $E_r$. At any rate, doing the recursion manually gives $$E_6={1223\over324}\doteq 3.77\ .$$