Sunday, January 29, 2017

coupon collector - What is the probability of rolling $n$ dice until each side appears at least once?



We roll a die until each side appears at least once, then we stop.




What is the probability of rolling exactly $n$ dice?





I guess the answer is
$$6-6\left(\dfrac{5}{6}\right)^n\;,$$



but this may be wrong.



In trying to solve this problem, I read this paper, but I couldn't solve the problem.


Answer



I'm going to assume that what you are asking is: if we roll a die until all sides (i.e. faces) appear, what is the probability that we will roll $n$ times?



In order for this to happen, we need exactly five faces to have appeared in the first $n-1$ rolls, and then the one missing face must appear on the $n$-th roll. Using inclusion-exclusion, we can express this, for $n>1$, as

$$
p(n) = \frac{1}{6} \binom{6}{5} \left( \left(\frac{5}{6} \right)^{n-1} - \binom{5}{4} \left( \frac{4}{6} \right)^{n-1} + \binom{5}{3} \left( \frac{3}{6}\right)^{n-1} - \binom{5}{2} \left( \frac{2}{6} \right)^{n-1}+\binom{5}{1} \left( \frac{1}{6}\right) ^{n-1} \right)
$$
So, for example, $p(6)=5/324$, $p(7)=25/648$, and $p$ hits a maximum of $875/10368$ at $n=11$.



As a check, you can (numerically) verify that
$$ \sum_{i=6}^{\infty} ip(i) = 14.7,$$
the well-known expected number of throws needed to see all faces.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...