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
66(56)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 n1 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...