I need to know how many times I should expect to need to roll an $n$-sided fair die to get each of $m$ (where $m < n$) outcomes at least once.
In my specific example I have a $7$ possible outcomes, of which I want to achieve $3$, with order being irrelevant.
Please excuse if this has been answered before, I searched but all I could find were answers for how many rolls you need to get one specific outcome, or every possible one, nothing for a subset of the possible outcomes and I couldn't figure out how to generalize those answers to apply to my problem.
Answer
Define the event that any occurance of the $m$ desired sides to be success. The probability of success would be $\frac{m}{n}$. This is a geometric distribution.
After the occurance of one the desired side, remove that side from our success set. Now define our event of success to be any occurance of the remaining $m-1$ sides. Again this is a geometric distribution, but with probability of success being $\frac{m-1}{n}$.
We can repeat this process for all the $m$ sides.
Hence expected number of trials is
$$\frac{n}{m}+\frac{n}{m-1}+\ldots \frac{n}{m-(m-1)}=\sum_{l=0}^{m-1}\frac{n}{m-l}=\sum_{l=1}^m\frac{n}{l}$$
For your specific example,
the answer should be $$\frac{7}{1}+\frac{7}{2}+\frac{7}{3}$$
No comments:
Post a Comment