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 mn. 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 m−1n.
We can repeat this process for all the m sides.
Hence expected number of trials is
nm+nm−1+…nm−(m−1)=m−1∑l=0nm−l=m∑l=1nl
For your specific example,
the answer should be 71+72+73
No comments:
Post a Comment