Saturday, December 7, 2019

probability - What is the expected number of rolls to get a subset of all possibilities?




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 m1 sides. Again this is a geometric distribution, but with probability of success being m1n.




We can repeat this process for all the m sides.



Hence expected number of trials is



nm+nm1+nm(m1)=m1l=0nml=ml=1nl



For your specific example,



the answer should be 71+72+73


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...