Expected number of tosses before you see a repeat.

Question

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?

Answer 1

Start with $n$-sided fair die and take $k=2$ (i.e. waiting till a face shows up twice).

For $i=0,1,\ldots,n$ look at the situation in which exactly $i$ faces have not shown up yet, and denote the expectation of the number of rolls yet to come by $\mu_{n,i}$. Then we have the relation:

$\mu_{n,i}=\frac{n-i}{n}\times1+\frac{i}{n}\times\left(1+\mu_{n,i-1}\right)=1+\frac{i}{n}\mu_{n,i-1}$ for $i=1,\ldots,n$.

Here $\mu_{n,0}=1$ and you are looking for $\mu_{n,n}$.

Based on this relation it is easy to show that:

$\mu_{n,i}=\frac{i!}{n^{i}}\times\sum_{j=0}^{i}\frac{n^{j}}{j!}$

So we have:

$\mu_{n,n}=\frac{n!}{n^{n}}\times\sum_{j=0}^{n}\frac{n^{j}}{j!}$

Answer 2

The expected number of rolls until the first $k$-repetition with an $n$-sided die is given by the integral $$\mathbb{E}(T) = \int_0^\infty \left(\sum_{j=0}^{k-1} {1\over j!}\left({x\over n}\right)^j\right)^n \,e^{-x}\,dx. $$

In my answers to the questions below I explain why.

How many expected people needed until 3 share a birthday?

Variance of time to find first duplicate

Answer 3

The probability of surviving the $k^\text{th}$ roll is $$ \frac{n-k+1}n\tag{1} $$ Therefore, the probability of surviving the first $k$ rolls is $$ P_n(k)=\frac{n!}{n^k(n-k)!}\tag{2} $$ The probability of stopping on roll $k$ is $$ P_n(k-1)-P_n(k)\tag{3} $$ and the expected duration is $$ \begin{align} E(n) &=\sum_{k=1}^\infty k(P_n(k-1)-P_n(k))\\ &=\sum_{k=0}^\infty(k+1)P_n(k)-\sum_{k=1}^\infty kP_n(k)\\ &=\sum_{k=0}^\infty(k+1)P_n(k)-\sum_{k=0}^\infty kP_n(k)\\ &=\sum_{k=0}^\infty P_n(k)\\ &=\sum_{k=0}^n\frac{n!}{n^k(n-k)!}\\ &=\frac{n!}{n^n}\sum_{k=0}^n\frac{n^k}{k!}\tag{4} \end{align} $$ As shown in this answer, $$ \sum_{k=0}^n\frac{n^k}{k!}=\frac12e^n\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-3/2}\right)\right)\tag{5} $$

Therefore, combining $(4)$, $(5)$, and Stirling's Formula yields $$ \begin{align} E(n) &=\frac12e^n\frac{n!}{n^n}\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-3/2}\right)\right)\\ &=\sqrt{\frac{\pi n}{2}}\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-1}\right)\right)\\ &=\sqrt{\frac{\pi n}{2}}+\frac23+O\left(n^{-1/2}\right)\tag{6} \end{align} $$ Extending the argument in the answer cited for $(5)$, we get $$ E(n)\in\left[\sqrt{\frac{\pi n}{2}}+\frac23,\sqrt{\frac{\pi n}{2}}+\frac23+\sqrt{\frac{\pi}{288n}}\right]\tag{7} $$

Answer 4

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