Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.